II.[SDOI2011]消耗战
老套路，我们建出虚树。
这题虚树中的边是带边权的，边权为原树中两点路径中权值的\(\min\)。这个权值的\(\min\)可以通过倍增求出。
在建出虚树后，我们就可以考虑DP了。设当前点为\(x\)，\(f_x\)为\(x\)同\(x\)子树中所有“资源丰富”节点切断的最小代价。
如果\(x\)本身是“资源丰富”的点，那直接return，不需要访问子树；
否则，我们需要访问子树。设\(y\)为\(x\)的一个儿子，\((x,y)\)的边权为\(z\)。
如果\(y\)是资源节点，\(f_x\)应该增加\(z\)；
否则，因为\(y\)节点可以在\((x,y)\)边处或者\(y\)子树内切断，\(f_x\)应该增加\(\min(z,f_y)\)。
则最终答案即为\(f_1\)。
复杂度\(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,dfn[250010],dep[250010],tot,anc[250010][20],mn[250010][20];
namespace real{
int head[250010],cnt;
struct node{
int to,next,val;
}edge[500010];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void dfs(int x){
dfn[x]=++tot;
for(int i=head[x],y;i!=-1;i=edge[i].next)if((y=edge[i].to)!=anc[x][0])dep[y]=dep[x]+1,anc[y][0]=x,mn[y][0]=edge[i].val,dfs(y);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])x=anc[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
int route(int x,int y){
int res=0x3f3f3f3f;
for(int i=19;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])res=min(res,mn[x][i]),x=anc[x][i];
return res;
}
namespace imag{
int head[250010],cnt,stk[250010],tp,a[250010];
ll f[250010];
bool mark[250010];
struct node{
int to,next,val;
}edge[250010];
void ae(int u,int v){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=route(v,u),head[u]=cnt++;
}
void ins(int x){
mark[x]=true;
if(!tp){stk[++tp]=x;return;}
int lca=LCA(x,stk[tp]);
while(tp>=2&&dep[lca]<dep[stk[tp-1]])ae(stk[tp-1],stk[tp]),tp--;
if(tp&&dep[lca]<dep[stk[tp]])ae(lca,stk[tp--]);
if(!tp||stk[tp]!=lca)stk[++tp]=lca;
stk[++tp]=x;
}
void fin(){
while(tp>=2)ae(stk[tp-1],stk[tp]),tp--;
tp--;
}
bool cmp(int x,int y){
return dfn[x]<dfn[y];
}
void dfs1(int x){
if(mark[x])return;
for(int i=head[x];i!=-1;i=edge[i].next){
dfs1(edge[i].to);
if(mark[edge[i].to])f[x]+=edge[i].val;
else f[x]+=min(1ll*edge[i].val,f[edge[i].to]);
}
}
void dfs2(int x){
mark[x]=false,f[x]=0;
for(int i=head[x];i!=-1;i=edge[i].next)dfs2(edge[i].to);
head[x]=-1;
}
void work(){
int q;
scanf("%d",&q);
for(int i=1;i<=q;i++)scanf("%d",&a[i]);
sort(a+1,a+q+1,cmp);
stk[++tp]=1;
for(int i=1;i<=q;i++)ins(a[i]);
fin();
dfs1(1);
printf("%lld\n",f[1]);
dfs2(1),cnt=0;
}
}
int main(){
scanf("%d",&n),memset(real::head,-1,sizeof(real::head)),memset(imag::head,-1,sizeof(imag::head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),real::ae(x,y,z);
real::dfs(1);
for(int j=1;j<20;j++)for(int i=1;i<=n;i++)anc[i][j]=anc[anc[i][j-1]][j-1],mn[i][j]=min(mn[i][j-1],mn[anc[i][j-1]][j-1]);
scanf("%d",&m);
while(m--)imag::work();
return 0;
}