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

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=300010;
const int INF=1000000000;
int cntE,fir[maxn],to[maxn*2],nxt[maxn*2];

void addedge(int a,int b){
    nxt[++cntE]=fir[a];
    fir[a]=cntE;
    to[cntE]=b;
}

int fa[maxn][20],dep[maxn];
int sz[maxn],son[maxn];
void DFS(int x){
    sz[x]=1;
    for(int k=0;
		(fa[x][k+1]=fa[fa[x][k]][k]);
			k++);
    for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x][0]){
			fa[to[i]][0]=x;
			dep[to[i]]=dep[x]+1;
			DFS(to[i]);
			sz[x]+=sz[to[i]];
			if(sz[to[i]]>sz[son[x]])
				son[x]=to[i];
    	}
}

int rID[maxn],tot;
int top[maxn],ID[maxn];

void DFS(int x,int tp){
	top[x]=tp;
    ID[x]=++tot;rID[tot]=x;
    if(son[x])DFS(son[x],tp);
    for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x][0]&&to[i]!=son[x])
			DFS(to[i],to[i]);
}

int Lca(int x,int y){
    while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]][0];
    }
    if(dep[x]<dep[y])
		swap(x,y);
    return y;  
}

int Get(int y,int d){
    while(dep[top[y]]>d)
		y=fa[top[y]][0];
    int dis=dep[y]-d;        
    for(int i=20;i>=0;i--)
		if(dis>>i&1)y=fa[y][i];
    return y; 
}

pair<int,int>g[maxn];
int h[maxn],mem[maxn];
int ans[maxn],t[maxn];
int st[maxn],pre[maxn],val[maxn];
int n,m,Q,tp;
int main(){
#ifndef ONLINE_JUDGE
	freopen("worldtree.in","r",stdin);
	freopen("worldtree.out","w",stdout);
#endif	
    scanf("%d",&n);
    for(int i=1,a,b;i<n;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
    }
    dep[1]=1;
    DFS(1);DFS(1,1);
    scanf("%d",&Q);
    while(Q--){
		scanf("%d",&m);tot=0;
		for(int i=1;i<=m;i++){
			scanf("%d",&h[i]);mem[i]=h[i];
			g[h[i]]=make_pair(0,h[i]);
			ans[h[i]]=0;h[i]=ID[h[i]];
			t[++tot]=h[i];
		}
		sort(h,h+m+1);tp=0;
		for(int i=1;i<=m;i++)
			h[i]=rID[h[i]];
		for(int i=1;i<=m;i++){
			if(i==1)
				pre[st[++tp]=h[i]]=0;
			else{
				int p=h[i],lca=Lca(p,st[tp]);
				for(;dep[st[tp]]>dep[lca];tp--)
					if(dep[st[tp-1]]<=dep[lca])
				pre[st[tp]]=lca;
				if(st[tp]!=lca){      
					t[++tot]=ID[lca];
					g[lca]=make_pair(INF,0);
					pre[lca]=st[tp];
					st[++tp]=lca;
				}
			pre[p]=st[tp];
			st[++tp]=p;
			}        
		}       
		sort(t+1,t+tot+1);
		for(int i=1;i<=tot;i++)
			t[i]=rID[t[i]];
		for(int i=1;i<=tot;i++){
			int p=t[i],f=pre[p];
			if(i==1)val[p]=n;
			else{
				val[p]=sz[p];
				val[f]-=sz[Get(p,dep[f]+1)];
			}
		}
		for(int i=tot;i>1;i--){
			int p=t[i],f=pre[p],w=dep[p]-dep[f];
			g[f]=min(g[f],make_pair(g[p].first+w,g[p].second));
		}
		for(int i=2;i<=tot;i++){
			int p=t[i],f=pre[p],w=dep[p]-dep[f];
			g[p]=min(g[p],make_pair(g[f].first+w,g[f].second));
		} 
		ans[g[t[1]].second]+=val[t[1]];
		for(int i=2;i<=tot;i++){
			int p=t[i],f=pre[p];
			ans[g[p].second]+=val[p];
			if(g[p].second==g[f].second)
				ans[g[p].second]+=sz[Get(p,dep[f]+1)]-sz[p];
			else{
				int da=dep[f],db=dep[p],mid;
				if(g[f].first>g[p].first)
					db-=g[f].first-g[p].first;
				if(g[f].first<g[p].first)
					da+=g[p].first-g[f].first;
				mid=(da+db+1)/2;
				mid+=((db-da)%2==0&&g[f].second<g[p].second)?1:0;
				int q=Get(p,mid);
				ans[g[p].second]+=sz[q]-sz[p];
				ans[g[f].second]+=sz[Get(p,dep[f]+1)]-sz[q];
			}        
		} 
		for(int i=1;i<=m;i++){
			printf("%d ",ans[mem[i]]);
			ans[mem[i]]=0;
		}
		printf("\n");      
    }
    return 0;
}