巨佬求调,样例1、2、4行对了,但3、5行全输出0
#include<bits/stdc++.h>
using namespace std;
#define INF 2147483647
const int N=3e5+10;
struct Edge{
int v,next;
}e1[N<<1],e2[N<<1];
int head1[N<<1],tot1,head2[N<<1],tot2;
inline int add1(int u,int v)
{
tot1++;
e1[tot1].v=v; e1[tot1].next=head1[u];
head1[u]=tot1;
}
inline int add2(int u,int v)
{
tot2++;
e2[tot2].v=v; e2[tot2].next=head2[u];
head2[u]=tot2;
}
int n,m,q,a[N],k[N];
int g[N],dp[N],ans[N];
bool vis[N];
int u,v;
int idx,dep[N],dfn[N],siz[N],fa[N][20];
int top,sta[N];
inline bool cmp(int x,int y)
{
return dfn[x]<dfn[y];
}
inline void dfs(int u)
{
dfn[u]=++idx; siz[u]=1;
for(int i=1;i<=19;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head1[u];i;i=e1[i].next)
{
int e=e1[i].v;
if(e!=fa[u][0])
{
fa[e][0]=u;
dep[e]=dep[u]+1;
dfs(e);
siz[u]+=siz[e];
}
}
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline void insert(int u)
{
if(top==0)
{
top=1;
sta[top]=u;
return ;
}
int l=lca(sta[top],u);
while(top>1&&dep[l]<dep[sta[top-1]])
{
add2(sta[top-1],sta[top]);
add2(sta[top],sta[top-1]);
top--;
}
if(dep[l]<dep[sta[top]])
{
add2(l,sta[top]);
add2(sta[top],l);
top--;
}
if(top==0||sta[top]!=l) sta[++top]=l;
top++; sta[top]=u;
}
inline void dfs1(int u,int f)
{
dp[u]=INF;
for(int i=head2[u];i;i=e2[i].next)
{
int e=e2[i].v;
if(e==f) continue;
dfs1(e,u);
int dis=dep[e]-dep[u];
if(dp[e]+dis<dp[u]) dp[u]=dp[e]+dis,g[u]=g[e];
else if(dp[e]+dis==dp[u]) g[u]=min(g[u],g[e]);
}
if(vis[u]) dp[u]=0,g[u]=u;
}
inline void calc(int x,int y)
{
int u=y,e=y;
for(int i=19;i>=0;i--)
if(dep[fa[u][i]]>dep[x]) u=fa[u][i];
ans[g[x]]-=siz[u];
for(int i=19;i>=0;i--)
{
int llen=dep[y]-dep[fa[e][i]]+dp[y],rlen=dep[fa[e][i]]-dep[x]+dp[x];
if(dep[fa[e][i]]>dep[x]&&(llen<rlen||(llen==rlen&&g[y]<g[x]))) e=fa[e][i];
}
ans[g[y]]+=siz[e]-siz[y]; ans[g[x]]+=siz[u]-siz[e];
}
inline void dfs2(int u,int f)
{
for(int i=head2[u];i;i=e2[i].next)
{
int e=e2[i].v;
if(e==f) continue;
int dis=dep[e]-dep[u];
if(dp[u]+dis<dp[u]) dp[e]=dp[u]+dis,g[e]=g[u];
else if(dp[u]+dis==dp[e]) g[e]=min(g[e],g[u]);
calc(u,e);
dfs2(e,u);
}
ans[g[u]]+=siz[u];
vis[u]=0; head2[u]=0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add1(u,v); add1(v,u);
}
dep[1]=1;
dfs(1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&q);
for(int j=1;j<=q;j++)
{
scanf("%d",&a[j]);
vis[a[j]]=1; ans[a[j]]=0;
k[j]=a[j];
}
sort(a+1,a+q+1,cmp);
tot2=0;
top=1; sta[top]=a[1];
for(int j=2;j<=q;j++)
insert(a[j]);
while(top>1)
{
add2(sta[top],sta[top-1]);
add2(sta[top-1],sta[top]);
top--;
}
dfs1(1,0); dfs2(1,0);
for(int j=1;j<=q;j++)
printf("%d ",ans[k[j]]);
printf("\n");
}
return 0;
}