bzoj2286 [Sdoi2011]消耗战

Description

Input

第一行一个整数n，代表岛屿数量。

接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。

第n+1行，一个整数m，代表敌方机器能使用的次数。

接下来m行，每行一个整数k_i，代表第i次后，有k_i个岛屿资源丰富，接下来k个整数h₁,h₂,…h_k，表示资源丰富岛屿的编号。

Output

输出有m行，分别代表每次任务的最小代价。

Sample Input

Sample Output

HINT

 对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

正解：虚树+树形dp。

闲得无聊学了下虚树。虚树就是说对于每个询问有k个点，满足sigma(k)为线性的问题，可以将每次询问的点提出来新建一棵树。对于k个结点，可以证明两两之间本质不同的lca最多只有k-1个。所以再把他们的lca全部加进去，再加一个公共的lca就行了（这道题是加1）。然后把这些结点按照dfs序从小到大排序，找出两个相邻点的lca。再将它们按照dfs序排序，开一个栈，如果栈顶元素是当前待加入结点的祖先，就连一条边，否则弹出栈顶，然后把当前结点加入栈中。这样，我们就能成功地建立一棵虚树了。这题dp还是挺容易的，然而因为邻接表清零出问题了然后调了半天。。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1e17)#define N (1000010)#define il inline#define RG  #define ll long long#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;struct edge{ int nt,to,dis; }g[N];int head[N],size[N],dfn[N],ed[N],dep[N],top[N],fa[N],son[N],a[N],st[N],vi[N],n,q,num,cnt;ll dis[N];il int gi(){    RG int x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il void insert(RG int from,RG int to,RG int dis){ g[++num]=(edge){head[from],to,dis},head[from]=num; return; }il int cmp(const int &a,const int &b){ return dfn[a]<dfn[b]; }il void dfs1(RG int x,RG int p){    dfn[x]=++cnt,dep[x]=dep[p]+1,fa[x]=p,size[x]=1; RG int v;    for (RG int i=head[x];i;i=g[i].nt){	v=g[i].to; if (v==p) continue;	dis[v]=min(dis[x],(ll)g[i].dis);	dfs1(v,x); size[x]+=size[v];	if (size[son[x]]<=size[v]) son[x]=v;    }    ed[x]=cnt; return;}il void dfs2(RG int x,RG int p,RG int a){    top[x]=a; if (son[x]) dfs2(son[x],x,a);    for (RG int i=head[x];i;i=g[i].nt){	RG int v=g[i].to;	if (v==p || v==son[x]) continue;	dfs2(v,x,v);    }    head[x]=0; return;}il int lca(RG int u,RG int v){    while (top[u]!=top[v]){	if (dep[top[u]]<dep[top[v]]) swap(u,v);	u=fa[top[u]];    }    return dep[u]<dep[v] ? u : v;}il ll dp(RG int x){    if (vi[x]) return dis[x]; RG ll res=0;    for (RG int i=head[x];i;i=g[i].nt) res+=dp(g[i].to);    return min(res,dis[x]);}il void work(){    n=gi(); RG int u,v,w; for (RG int i=1;i<n;++i) u=gi(),v=gi(),w=gi(),insert(u,v,w),insert(v,u,w);    dis[1]=inf,dfs1(1,0),dfs2(1,0,1); q=gi();    while(q--){	RG int k=gi(),M=k; for (RG int i=1;i<=k;++i) vi[a[i]=gi()]=1; sort(a+1,a+k+1,cmp);	for (RG int i=2;i<=k;++i) if (ed[a[i-1]]<dfn[a[i]]) a[++M]=lca(a[i-1],a[i]); a[++M]=1;	sort(a+1,a+M+1,cmp); M=unique(a+1,a+M+1)-a-1; RG int top=1; st[top]=a[1],num=0;	for (RG int i=2;i<=M;++i){	    while (top && ed[st[top]]<dfn[a[i]]) top--;	    insert(st[top],a[i],0),st[++top]=a[i];	}	PRintf("%lld/n",dp(1)); for (RG int i=1;i<=M;++i) vi[a[i]]=head[a[i]]=0;    }    return;}int main(){    File("war");    work();    return 0;}