http://www.lydsy.com/JudgeOnline/problem.php?id=3572
思路:建立虚树，然后可以发现，每条边不是同归属于一端，那就是切开，一半给上面，一半给下面。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define N 300005
int tot,go[N*],next[N*],first[N],sz,deep[N],tmp[N],tree[N];
int son[N],dfn[N],fa[N][],bin[],ask[N],In[N],st[N],n,m,ans[N];
int father[N],val[N];
std::pair<int,int>near[N];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);insert(y,x);
}
void dfs(int x){
son[x]=;
dfn[x]=++sz;
for (int i=;i<=;i++)
fa[x][i]=fa[fa[x][i-]][i-];
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa[x][]) continue;
deep[pur]=deep[x]+;
fa[pur][]=x;
dfs(pur);
son[x]+=son[pur];
}
}
int find(int x,int dep){
for (int i=;i>=;i--)
if (deep[fa[x][i]]>=dep) x=fa[x][i];
return x;
}
int lca(int x,int y){
if (deep[x]<deep[y]) std::swap(x,y);
int t=deep[x]-deep[y];
for (int i=;i<=;i++)
if (t&bin[i])
x=fa[x][i];
if (x==y) return x;
for (int i=;i>=;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][];
}
bool cmp(int a,int b){
return dfn[a]<dfn[b];
}
void solve(){
m=read();
for (int i=;i<=m;i++){
ask[i]=read(),tmp[i]=tree[i]=ask[i];
near[ask[i]]=std::make_pair(,ask[i]);
ans[ask[i]]=;
}
std::sort(ask+,ask++m,cmp);
int top=,all=m;
for (int i=;i<=m;i++){
int p=ask[i];
if (!top) father[p]=,st[++top]=p;
else{
int x=lca(st[top],p);
father[p]=x;
while (top&&deep[st[top]]>deep[x]){
if (deep[st[top-]]<=deep[x]){
father[st[top]]=x;
}
top--;
}
if (st[top]!=x){
father[x]=st[top];tree[++all]=x;
st[++top]=x;near[x]=std::make_pair(<<,);
}
st[++top]=p;
}
}
std::sort(tree+,tree++all,cmp);
for (int i=;i<=all;i++){
int p=tree[i],f=father[p];
val[p]=son[p];
if (i>) In[p]=deep[p]-deep[f];
}
for (int i=all;i>;i--){
int p=tree[i],f=father[p];
near[f]=std::min(near[f],std::make_pair(near[p].first+In[p],near[p].second));
}
for (int i=;i<=all;i++){
int p=tree[i],f=father[p];
near[p]=std::min(near[p],std::make_pair(near[f].first+In[p],near[f].second));
}
for (int i=;i<=all;i++){
int p=tree[i],f=father[p],sum=son[find(p,deep[f]+)]-son[p];
if (f==) ans[near[p].second]+=n-son[p];
else{
val[f]-=sum+son[p];
if (near[p].second==near[f].second) ans[near[p].second]+=sum;
else{
int dis=(deep[p]-deep[f]-near[p].first+near[f].first)/;
if (dis+near[p].first==near[f].first+deep[p]-deep[f]-dis&&near[f].second<near[p].second) dis--;
int x=find(p,deep[p]-dis);
ans[near[p].second]+=son[x]-son[p];
ans[near[f].second]+=sum+son[p]-son[x];
}
}
}
for (int i=;i<=all;i++){
ans[near[tree[i]].second]+=val[tree[i]];
}
for (int i=;i<=m;i++)
printf("%d ",ans[tmp[i]]);
puts("");
}
int main(){
n=read();
bin[]=;
for (int i=;i<=;i++) bin[i]=bin[i-]*;
for (int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
dfs();
int T=read();
while (T--) solve();
}