Sdoi2011消耗戰
題意：
給一棵帶權樹，1為根，q次詢問，每次詢問給出k個特殊點，要求去掉一些邊，代價是權值，讓點1不能到達k裡的任意一個，輸出最小代價。
題解：
首先考慮單次詢問，容易想到dp[x]表示讓1不能到x子樹裡的特殊點的代價。
當x是特殊點的時候，顯然有dp[x]= min(path[x])，表示x到根節點的最小的那條邊，因為一定要去掉x。
當x不是的時候，dp[x]=min(path[x], sum(dp[son(x)]))，表示要麼去掉x，要麼去掉x所有兒子的子樹的特殊點。
答案就是dp[1]。
現在變成多次詢問，但是總的特殊點不超過 105 ，需要用到虛樹的技巧。
看了幾篇blog學了一下虛樹，這篇的寫法很不錯。
照着思路寫就行了，代碼還是比較容易的。
#include<bits/stdc++.h>
using namespace std;
const int N = +;
typedef long long ll;
typedef pair<int,ll> edg;
const ll inf = ~ll>>;
vector<edg>G[N];
vector<int>qry, GG[N];
ll cost[N];
int dep[N], fa[N][], in[N], cnt = ;
int st[N], top;
bool vis[N];
inline bool cmp(const int& a, const int& b){
return in[a] < in[b];
}
void dfs1(int rt, int f){
in[rt] = ++cnt;
for(int i = ; i < ; ++i){
if(dep[rt] < (<<i)) break;
fa[rt][i] = fa[fa[rt][i-]][i-];
}
for(int i = ; i < G[rt].size(); ++i){
int v = G[rt][i].first;
if(v == f) continue;
cost[v] = min(cost[rt], G[rt][i].second);
dep[v] = dep[rt]+;
fa[v][] = rt;
dfs1(v, rt);
}
}
int lca(int a, int b){
if(dep[a] < dep[b]) swap(a, b);
int delt = dep[a] - dep[b];
for(int i = ; i < ; ++i){
if(delt&(<<i)) a = fa[a][i];
}
for(int i = ; i >= ; --i){
if(fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
}
if(a != b) return fa[a][];
else return a;
}
void add(int a, int b){
if(a == b) return;
GG[a].push_back(b);
}
ll dp[N];
void solve(int rt){
dp[rt] = cost[rt];
if(!vis[rt]){
ll sum = ;
for(int i = ; i < GG[rt].size(); ++i){
solve(GG[rt][i]);
sum += dp[GG[rt][i]];
}
dp[rt] = min(dp[rt], sum);
}
}
int main(){
int n;
scanf("%d", &n);
for(int a, b, c, i = ; i < n; ++i){
scanf("%d%d%d", &a, &b, &c);
G[a].push_back(edg(b, c));
G[b].push_back(edg(a, c));
}
cost[] = inf;
dfs1(, );
int q;
scanf("%d", &q);
while(q--){
qry.clear();
int k;
scanf("%d", &k);
for(int a, i = ; i < k; ++i){
scanf("%d", &a);
qry.push_back(a);
vis[a] = ;
}
sort(qry.begin(), qry.end(), cmp);
int len = qry.size();
for(int i = ; i < len; ++i){
qry.push_back(lca(qry[i], qry[i-]));
}
qry.push_back();
sort(qry.begin(), qry.end(), cmp);
qry.erase(unique(qry.begin(), qry.end()), qry.end());
int top = ;
for(int i = ; i < qry.size(); ++i){
while(top > && lca(st[top], qry[i]) != st[top]) top--;
if(top) add(st[top], qry[i]);
st[++top] = qry[i];
}
solve();
for(int i = ; i < qry.size(); ++i) GG[qry[i]].clear(), vis[qry[i]] = ;
printf("%lld\n", dp[]);
}
}