G - 消耗战
题意
??一棵有n个节点的树，删除一条边的代价是
Wi
??有Q个询问，每个询问给出Ki 个点，我们可以删除若干条边使得这些点与根节点（1号点）不连通，求最小代价
解法
虚树+树型DP：
??首先设fu表示解决掉u及u 的子树的最小花费，Vu表示u的父边的边权，那么显然有：
fu=min（∑fv，Vu），v 为u的孩子
这样做的话，每一次都需要遍历整棵树，所以复杂度是O（Qn ）
??可以发现，在进行dfs的时候，会经过很多没有用的点，所以考虑将这些点去掉，留下需要用到的点，那么这个过程就是构建一棵虚树，这样的话，复杂度就可以变为O（∑Ki?logn）
??所以本题的重点就变成了怎么构建虚树，这里推荐一个博客，大家可以看看：http://www.cnblogs.com/chenhuan001/p/5639482.html
复杂度
O（∑Ki?logn）
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define Rint register int
#define Lint long long int
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=250010;
struct node
{int next,to,w;
}t[MAXN*2];
int head[MAXN],num;
int fa[MAXN][20],w[MAXN][20];
int dep[MAXN],island[MAXN];
int dfn[MAXN],q[MAXN];
Lint f[MAXN],g[MAXN];
int n,m,k,top,cnt;
void add(int u,int v,int w)
{t[++num]=(node){ head[u],v,w };head[u]=num;
}
void dfs(int k)
{dfn[k]=++cnt;for(int i=head[k],x; i ;i=t[i].next){x=t[i].to;if( dfn[x] ) continue ;dep[x]=dep[k]+1,fa[x][0]=k;w[x][0]=t[i].w;dfs( x );}
}
int LCA(int u,int v)
{if( dep[u]<dep[v] ) swap( u,v );int f=dep[u]-dep[v];for(int i=19;i>=0;i--)if( (1<<i)&f ) u=fa[u][i];if( u==v ) return u;for(int i=19;i>=0;i--)if( fa[u][i]!=fa[v][i] )u=fa[u][i],v=fa[v][i];return fa[u][0];
}
int get(int u,int v)
{int ret=INF;for(int i=19;i>=0;i--)if( fa[u][i] && dep[fa[u][i]]>=dep[v] ) ret=min( ret,w[u][i] ),u=fa[u][i];return ret;
}
void init()
{for(int j=1;j<=19;j++)for(int i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];w[i][j]=min( w[fa[i][j-1]][j-1],w[i][j-1] );}
}
int cmp(int x,int y)
{return dfn[x]<dfn[y];
}
int main()
{int u,v,w;scanf("%d",&n);for(int i=1;i<=n-1;i++){scanf("%d%d%d",&u,&v,&w);add( u,v,w ),add( v,u,w );}scanf("%d",&m);dfs( 1 ),init();while( m-- ){scanf("%d",&k),top=0;for(int j=1;j<=k;j++) scanf("%d",&island[j]);sort( island+1,island+k+1,cmp );q[++top]=1;f[1]=0,g[1]=0;for(int i=1;i<=k;i++){u=LCA( q[top],island[i] );while( dep[q[top]]>dep[u] )if( dep[q[top-1]]<=dep[u] ){w=min( g[top] ? INF : f[top] , (Lint)get( q[top],u ) );top--;if( u!=q[top] ) q[++top]=u,f[top]=g[top]=0;f[top]+=w;break ;}else{f[top-1]+=min( g[top] ? INF : f[top] , (Lint)get( q[top],q[top-1] ) );top--;}if( q[top]!=island[i] ) q[++top]=island[i],f[top]=0;g[top]=1;}while( top>1 ) f[top-1]+=min( g[top] ? INF : f[top] , (Lint)get( q[top],q[top-1] ) ),top--;printf("%lld\n",f[1]);}return 0;
}