记录编号	370929	评测结果	AAAAAAAAAA
题目名称	[HNOI 2014]世界树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.329 s
提交时间	2017-02-14 20:25:02	内存使用	138.21 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e6+10;
int n,w[N],head[N],tail[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int s[N],fa[N],pos[N],h[N];
void dfs(int x){
	static int cnt=0;
	pos[x]=++cnt;s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		fa[w[i]]=x;
		h[w[i]]=h[x]+1;
		dfs(w[i]);
		s[x]+=s[w[i]];
	}
}
int dp[N][20],t[20],lg[N];
void init_st(){
	t[0]=1;
	for (int i=1;i<20;i++){
		t[i]=1<<i;
		for (int j=t[i-1];j<N&&j<t[i];j++) lg[j]=i-1;
	}
	for (int i=1;i<=n;i++) dp[i][0]=fa[i];
	for (int j=1;j<20;j++)
	for (int i=1;i<=n;i++)
		dp[i][j]=dp[dp[i][j-1]][j-1];
}
int getfa(int x,int H){
	for (int d=h[x]-H;d;d-=d&-d) x=dp[x][lg[d&-d]];
	return x;
}
int lca(int x,int y){
	if (h[x]<h[y]) swap(x,y);
	x=getfa(x,h[y]);
	for (int i=19;x!=y;x=dp[x][i],y=dp[y][i])
		while (i&&dp[x][i]==dp[y][i]) i--;
	return x;
}
struct pt{
	int x;
	bool operator < (const pt &a)const{return pos[x]<pos[a.x];}
};
priority_queue<pt> H;
vector<int> E[300010];
int q[N],m,que[N],size,dis[N],ans[N],Min[N],color[N];
void visit(int x,int C){
	if (color[x]==C) return;
	color[x]=C;
	que[++size]=x;
	dis[x]=Min[x]=1e9;
	ans[x]=fa[x]=0;
	E[x].clear();
	H.push((pt){x});
}
int Dis(int x,int y){
	return h[x]>h[y]?h[x]-h[y]:h[y]-h[x];
}
queue<int> Q;
bool inq[N];
void spfa(){
	for (int i=1;i<=m;i++)
		Min[q[i]]=q[i],dis[q[i]]=0,Q.push(q[i]);
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		inq[v]=0;
		for (int i=E[v].size()-1;i>=0;i--){
			int u=E[v][i];
			bool ok=0;
			ok|=(dis[v]+Dis(u,v)<dis[u]);
			ok|=(dis[v]+Dis(u,v)==dis[u]&&Min[v]<Min[u]);
			if (ok){
				dis[u]=dis[v]+Dis(u,v);
				Min[u]=Min[v];
				if (!inq[u]) inq[u]=1,Q.push(u);
			}
		}
	}
	for (int i=1;i<=size;i++)
		ans[Min[que[i]]]+=s[que[i]];
	for (int i=1;i<=size;i++){
		int u=que[i],v=fa[u];
		if (!v){
			ans[Min[u]]+=n-s[u];
			continue;
		}
		int h1=h[u],h2=h[v],d1=dis[u],d2=dis[v];
		int h3=h1+h2+d1-d2;
		if (h3&1) h3=h3/2+1;else
			h3=Min[u]<Min[v]?h3/2:h3/2+1;
		if (h3>h1) h3=h1;
		if (h3<h2) h3=h2;
		int p=getfa(u,h3);
		ans[Min[u]]+=s[p]-s[u];
		ans[Min[v]]-=s[p];
	}
}
void build(){
	static int C=0;C++;size=0;
	for (int i=1;i<=m;i++) visit(q[i],C);
	while (!H.empty()){
		int v=H.top().x;H.pop();
		if (!H.empty()){
			int u=H.top().x;
			fa[v]=lca(u,v);
			visit(fa[v],C);
			E[v].push_back(fa[v]);
			E[fa[v]].push_back(v);
		}
	}
}
int main()
{
	freopen("worldtree.in","r",stdin);
	freopen("worldtree.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	h[1]=fa[1]=1;dfs(1);
	init_st();
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&m);
		for (int i=1;i<=m;i++) scanf("%d",&q[i]);
		build();spfa();
		for (int i=1;i<=m;i++) printf("%d ",ans[q[i]]);
		puts("");
	}
	return 0;
}