【ybt金牌導航5-3-2】【luogu P2495】消耗戰

消耗戰

題目連結：ybt金牌導航5-3-2 / luogu P2495

題目大意

有一個樹，每個邊有切斷的費用，每次選一些點（不會選 1 點），問你最少要用多少費用切邊，使得所有選點的點都不能與 1 點連通。

思路

首先容易想到如果一次詢問的話，它就是一個樹形 DP。

大概就是記錄每個點被割最少要多少費用（就是 1 1 1 點到它之間的邊之間邊權最小的那個），然後從葉節點從下而上 DP，可以割自己，也可以把子樹的都處理掉。

但是如果自己一定要割就沒有第二種，因為你割了自己又割兒子肯定不優。

但是它是多組詢問，那你就建個虛樹搞搞就好了。

（詢問虛樹上的距離不要用 LCA 來搞，我一開始是這麼搞的，然後卡了三頁評測的常也隻有 90 90 90）

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct node {
	ll x;
	int to, nxt;
}e[500001], e_[250001];
struct kong {
	int fa;
}t[250001];
int n, x, y, z, le[250001], KK, lca, tmpp;
int fa[250001][18], dfn[250001], m, nn;
int sta[250001], deg[250001];
int le_[250001], KK_, sp[250001];
ll f[250001], minv[250001], re;
bool real[500001];

inline int read() {
	re = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') {
		re = (re << 3) + (re << 1) + c - '0';
		c = getchar();
	}
	return re;
}

inline void write(ll x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

inline ll Min(ll x, ll y) {
	return (x < y) ? (x) : (y);
}

inline void add(int x, int y, ll z) {
	e[++KK] = (node){z, y, le[x]}; le[x] = KK;
	e[++KK] = (node){z, x, le[y]}; le[y] = KK;
}

inline void add_(int x, int y) {
	e_[++KK_] = (node){0, y, le_[x]}; le_[x] = KK_;
}

void dfs(int now, int father) {
	deg[now] = deg[father] + 1;
	fa[now][0] = father;
	dfn[now] = ++tmpp;
	for (int i = le[now]; i; i = e[i].nxt)
		if (e[i].to ^ father) {
			minv[e[i].to] = Min(minv[now], e[i].x);//求出割這個點最少要的費用（選 1 點到它費用最小的邊）
			dfs(e[i].to, now);
		}
}

inline bool cmp(int x, int y) {//按 dfs 序排序
	return dfn[x] < dfn[y];
}

inline int LCA(int x, int y) {//求LCA
	if (deg[x] < deg[y]) swap(x, y);
	for (int i = 15; i >= 0; i--)
		if (deg[fa[x][i]] >= deg[y])
			x = fa[x][i];
	if (x == y) return x;
	for (int i = 15; i >= 0; i--)
		if (fa[x][i] ^ fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	return fa[x][0];
}

void build_kong() {//建虛樹
	tmpp = 0;
	sort(sp + 1, sp + sp[0] + 1, cmp);
//	nn = unique(sp + 1, sp + sp[0] + 1) - sp - 1;
	nn = sp[0];
	sta[0] = 1;
	for (int i = 1; i <= nn; i++) {
		if (!tmpp) {
			sta[++tmpp] = sp[i];
			t[sp[i]].fa = 0;
		}
		else {
			lca = LCA(sp[i], sta[tmpp]);
			while (deg[lca] < deg[sta[tmpp]]) {
				if (deg[lca] > deg[sta[tmpp - 1]]) {
					t[sta[tmpp]].fa = lca;
				}
				tmpp--;
			}
			while (lca ^ sta[tmpp]) {
				sp[++sp[0]] = lca;
				t[lca].fa = sta[tmpp];
				sta[++tmpp] = lca;
			}
			t[sp[i]].fa = lca;
			sta[++tmpp] = sp[i];
		}
	}
//	sort(sp + 1, sp + sp[0] + 1, cmp);
	for (int i = 1; i <= sp[0]; i++)
		if (sp[i] ^ 1)
			add_((t[sp[i]].fa) ? (t[sp[i]].fa) : 1, sp[i]);
}

void dfs_(int now, int father) {//樹狀 DP
	f[now] = minv[now];//這這裡（那下面的都可以不割）
	
	ll tmp = 0;
	for (int i = le_[now]; i; i = e_[i].nxt)
		if (e_[i].to ^ father) {
			dfs_(e_[i].to, now);
			tmp += f[e_[i].to];//選把下面割個的都割掉，不割這裡
		}
	
	if (!real[now]) f[now] = Min(f[now], tmp);//如果這個這個點要割，那不能隻割下面的，一定要選上面的割
	
	le_[now] = 0;
	real[now] = 0;
}

int main() {
//	freopen("read.txt", "r", stdin);
//	freopen("write.txt", "w", stdout);
	
	n = read();
	for (int i = 1; i < n; i++) {
		x = read(); y = read(); z = read();
		add(x, y, z);
	}
	
	tmpp = 0;
	minv[1] = 1e18;
	dfs(1, 0);
	for (int i = 1; i <= 15; i++)//倍增預處理LCA
		for (int j = 1; j <= n; j++)
			fa[j][i] = fa[fa[j][i - 1]][i - 1];
	
	m = read();
	while (m--) {
		sp[0] = read();
		for (int i = 1; i <= sp[0]; i++) {
			sp[i] = read();
			real[sp[i]] = 1;//标記哪些點是一定要隔開的
		}
		sp[++sp[0]] = 1;
		
		build_kong();//建虛樹
		
		dfs_(1, 0);
		
		write(f[1]);
		putchar('\n');
		
		KK_ = 0;
	}
	
	return 0;
}