在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。
第一行一个整数n，代表岛屿数量。
接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。
第n+1行，一个整数m，代表敌方机器能使用的次数。
接下来m行，每行一个整数ki，代表第i次后，有ki个岛屿资源丰富，接下来k个整数h1,h2,…hk，表示资源丰富岛屿的编号。
输出有m行，分别代表每次任务的最小代价。
树链剖分预处理出dfs序等并用zkw线段树维护链上最小值
对每个询问，将询问涉及的点按dfs序排序，相邻的取lca，重新连边（边权为原树路径上最小边权）构建针对询问的虚树，在虚树上dp即可
#include<cstdio> #include<algorithm> typedef long long lint; const int inf=2147483647; inline int read(){ int x=0,c=getchar(); while(c>‘9‘||c<‘0‘)c=getchar(); while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar(); return x; } inline int min(int a,int b){return a<b?a:b;} inline lint min(lint&a,lint&b){return a<b?a:b;} const int N=250005; int n,m,t; int as[N],bs[N],cs[N]; int stk[N*2],ks[N],p,p1; int mv[524288]; int e0[N],es[N*2],enx[N*2],ep=1; int dep[N],fa[N],son[N],sz[N],top[N],id[N],rid[N],idp=1; bool d[N]; void f1(int w,int pa){ fa[w]=pa; dep[w]=dep[pa]+1; sz[w]=1; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=pa){ f1(u,w); sz[w]+=sz[u]; if(sz[u]>sz[son[w]])son[w]=u; } } } void f2(int w,int tp){ top[w]=tp; id[w]=idp++; if(son[w])f2(son[w],tp); for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=fa[w]&&u!=son[w])f2(u,u); } rid[w]=idp; } int lca(int x,int y){ int a=top[x],b=top[y],c; while(a!=b){ if(dep[a]<dep[b])c=x,x=y,y=c,c=a,a=b,b=c; x=fa[a]; a=top[x]; } return dep[x]<dep[y]?x:y; } int getmin(int l,int r){ int v=inf; for(l+=262143,r+=262145;l^r^1;l>>=1,r>>=1){ if(~l&1)v=min(v,mv[l^1]); if(r&1)v=min(v,mv[r^1]); } return v; } int getev(int x,int y){ int a=top[x],b=top[y],v=inf; while(a!=b){ v=min(v,getmin(id[b],id[y])); y=fa[b];b=top[y]; } if(y!=x)v=min(v,getmin(id[x]+1,id[y])); return v; } lint dp(int w){ lint s=0; while(p1<p){ int u=stk[p1++]; if(u==w)continue; if(id[u]<=id[w]||id[u]>=rid[w]){--p1;break;} int v=getev(w,u); lint x=dp(u); if(d[u])s+=v; else s+=min(x,v); } return s; } inline bool cmp(int a,int b){ return id[a]<id[b]; } int main(){ n=read(); for(int i=1;i<n;i++){ as[i]=read(); bs[i]=read(); cs[i]=read(); es[ep]=bs[i];enx[ep]=e0[as[i]];e0[as[i]]=ep++; es[ep]=as[i];enx[ep]=e0[bs[i]];e0[bs[i]]=ep++; } f1(1,0);f2(1,1); for(int i=262144;i<524288;i++)mv[i]=inf; for(int i=1;i<n;i++){ int a=as[i],b=bs[i],c=cs[i]; if(fa[a]==b)mv[id[a]+262144]=c; else mv[id[b]+262144]=c; } for(int i=262143;i;i--)mv[i]=min(mv[i<<1],mv[i<<1^1]); m=read(); while(m--){ t=read(); for(int i=0;i<t;i++)ks[i]=read(); for(int i=0;i<t;i++)d[stk[i]=ks[i]]=1; p=t; stk[p++]=1; std::sort(stk,stk+p,cmp); for(int i=p-1;i>1;i--)stk[p++]=lca(stk[i],stk[i-1]); std::sort(stk,stk+p,cmp); p1=0; printf("%lld\n",dp(1)); for(int i=0;i<t;i++)d[ks[i]]=0; } return 0; }
原文：http://www.cnblogs.com/ccz181078/p/5295303.html