记录编号	281462	评测结果	AAAAAAAAAA
题目名称	[HNOI 2014]世界树	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	1.292 s
提交时间	2016-07-11 19:23:00	内存使用	24.32 MiB

#include<stdio.h>
#include<algorithm>
#define N 300010
#define inf 1000000000
int n,x,y,Q,m;
int shu,first[N];
struct edge{int v,nx;}o[N<<1];
inline void add(int u,int v){o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;}
int cnt,fa[N],size[N],dep[N],ord[N],son[N],top[N],seq[N];
int a[N],b[N],Fa[N],X[N],Y[N],st[N],p[N],Ans[N],val[N];
inline bool cmp(int x,int y){return ord[x]<ord[y];}
inline void dfs(int x){
	dep[x]=dep[fa[x]]+1,size[x]=1;
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==fa[x])continue;
		fa[o[i].v]=x,dfs(o[i].v),size[x]+=size[o[i].v];
		if(size[o[i].v]>size[son[x]])son[x]=o[i].v;
	}
}
inline void dfs(int x,int y){
	top[x]=y,ord[x]=++cnt,seq[cnt]=x;
	if(son[x])dfs(son[x],y);
	for(int i=first[x];i;i=o[i].nx){
		if(o[i].v==fa[x]||o[i].v==son[x])continue;
		dfs(o[i].v,o[i].v);
	}
}
inline int lca(int x,int y){
	for(;top[x]!=top[y];x=fa[top[x]])
	    if(dep[top[x]]<dep[top[y]])std::swap(x,y);
	return dep[x]<dep[y]?x:y;
}
inline int get(int x,int d){
	for(;dep[top[x]]>d;x=fa[top[x]]);
	return seq[ord[x]-dep[x]+d];
}
inline void Min(int x,int y,int z){
	if(X[x]>X[y]+z||(X[x]==X[y]+z&&Y[x]>Y[y]))
	    X[x]=X[y]+z,Y[x]=Y[y];
}
int main(){
	freopen("worldtree.in","r",stdin);
	freopen("worldtree.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<n;++i)scanf("%d%d",&x,&y),add(x,y),add(y,x);
	dfs(1),dfs(1,1);
	for(scanf("%d",&Q);Q--;){
		int cnt=0;
		scanf("%d",&m);
		for(int i=1;i<=m;++i)scanf("%d",&a[i]),p[++cnt]=b[i]=a[i],X[a[i]]=0,Y[a[i]]=a[i];
		std::sort(a+1,a+m+1,cmp);
		for(int i=1,tail=0;i<=m;++i)if(tail){
			int t=lca(st[tail],a[i]);
			for(;dep[st[tail]]>dep[t];--tail)
			    if(dep[st[tail-1]]<=dep[t])Fa[st[tail]]=t;
			if(st[tail]!=t)Fa[t]=st[tail],st[++tail]=p[++cnt]=t,X[t]=inf,Y[t]=0;
			st[++tail]=a[i],Fa[a[i]]=t;
		}else st[++tail]=a[i],Fa[a[i]]=0;
		std::sort(p+1,p+cnt+1,cmp);
		for(int i=cnt;i>1;--i)Min(Fa[p[i]],p[i],dep[p[i]]-dep[Fa[p[i]]]);
		for(int i=2;i<=cnt;++i)Min(p[i],Fa[p[i]],dep[p[i]]-dep[Fa[p[i]]]);
		for(int i=1;i<=cnt;++i){
			x=p[i],y=Fa[x],val[x]=size[x];
			if(i==1){
				Ans[Y[x]]+=n-size[x];
				continue;
			}
			int t=get(x,dep[y]+1),sum=size[t]-size[x];
			val[y]-=size[t];
			if(Y[x]==Y[y]){
				Ans[Y[x]]+=sum;
				continue;
			}
			t=X[x]-X[y]+dep[x]+dep[y]+2;
			if(t&1^1&&Y[y]>Y[x])t-=2;
			t>>=1;
			t=size[get(x,t)]-size[x];
			Ans[Y[x]]+=t,Ans[Y[y]]+=sum-t;
		}
		for(int i=1;i<=cnt;++i)
		    Ans[Y[p[i]]]+=val[p[i]];
		for(int i=1;i<=m;++i)printf("%d ",Ans[b[i]]),Ans[b[i]]=0;
		puts("");
	}
}