消耗战
题目链接：ybt金牌导航5-3-2 / luogu P2495
题目大意
有一个树，每个边有切断的费用，每次选一些点（不会选 1 点），问你最少要用多少费用切边，使得所有选点的点都不能与 1 点连通。
思路
首先容易想到如果一次询问的话，它就是一个树形 DP。
大概就是记录每个点被割最少要多少费用（就是 (1) 点到它之间的边之间边权最小的那个），然后从叶节点从下而上 DP，可以割自己，也可以把子树的都处理掉。
但是如果自己一定要割就没有第二种，因为你割了自己又割儿子肯定不优。
但是它是多组询问，那你就建个虚树搞搞就好了。
（询问虚树上的距离不要用 LCA 来搞，我一开始是这么搞的，然后卡了三页评测的常也只有 (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('
');
KK_ = 0;
}
return 0;
}