首先建虚树
DFS求虚树上每个点所属的点和到它所属点的距离，然后在=考虑虚树所有的边(对应原树一条链)。如果两个端点所属节点不同就倍增出分界点统计答案，否则不用管(之后会统计到的)；注意根节点特殊讨论。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=600005,K=20,inf=1e9; 6 int T,n,m,t1,t2,cnt,tot,top; 7 int p[N],noww[N],goal[N]; 8 int siz[N],dep[N],dfn[N],upt[N][K],oth[N][K]; 9 int a[N],b[N],c[N],d[N],bel[N],stk[N],ans[N]; 10 bool cmp(int a,int b) 11 { 12 return dfn[a]<dfn[b]; 13 } 14 void Link(int f,int t) 15 { 16 noww[++cnt]=p[f]; 17 goal[cnt]=t,p[f]=cnt; 18 } 19 void DFS(int nde,int fth,int dth) 20 { 21 siz[nde]=1,dep[nde]=dth; 22 upt[nde][0]=fth,dfn[nde]=++tot; 23 for(int i=1;i<=19&&upt[nde][i-1];i++) 24 upt[nde][i]=upt[upt[nde][i-1]][i-1]; 25 for(int i=p[nde];i;i=noww[i]) 26 if(goal[i]!=fth) 27 DFS(goal[i],nde,dth+1),siz[nde]+=siz[goal[i]]; 28 } 29 void Calc(int nde,int fth) 30 { 31 oth[nde][0]=siz[fth]-siz[nde]; 32 for(int i=1;i<=19&&upt[nde][i-1];i++) 33 oth[nde][i]=oth[nde][i-1]+oth[upt[nde][i-1]][i-1]; 34 for(int i=p[nde];i;i=noww[i]) 35 if(goal[i]!=fth) Calc(goal[i],nde); 36 } 37 int LCA(int x,int y) 38 { 39 if(dep[x]<dep[y]) swap(x,y); 40 for(int i=19;dep[x]!=dep[y];i--) 41 if(dep[upt[x][i]]>=dep[y]) x=upt[x][i]; 42 if(x==y) return x; 43 for(int i=19;~i;i--) 44 if(upt[x][i]!=upt[y][i]) 45 x=upt[x][i],y=upt[y][i]; 46 return upt[x][0]; 47 } 48 int Dis(int x,int y) 49 { 50 int lca=LCA(x,y); 51 return dep[x]+dep[y]-2*dep[lca]; 52 } 53 bool Check(int a,int b,int d) 54 { 55 return c[a]+d<c[b]||(c[a]+d==c[b]&&bel[a]<bel[b]); 56 } 57 void Insert(int nde) 58 { 59 if(!top) stk[++top]=nde; 60 else 61 { 62 int lca=LCA(nde,stk[top]); 63 if(lca!=stk[top]) 64 { 65 while(top>1&&dfn[lca]<=dfn[stk[top-1]]) 66 Link(stk[top-1],stk[top]),top--; 67 if(dfn[lca]<dfn[stk[top]]) 68 Link(lca,stk[top]),top--; 69 if(lca!=stk[top]) 70 stk[++top]=lca; 71 } 72 stk[++top]=nde; 73 } 74 } 75 int Upt(int nde,int gal) 76 { 77 int ret=0; 78 for(int i=19;~i;i--) 79 if(gal&(1<<i)) 80 ret+=oth[nde][i],nde=upt[nde][i]; 81 return ret; 82 } 83 void DFS1(int nde) 84 { 85 if(!bel[nde]) c[nde]=inf; 86 for(int i=p[nde];i;i=noww[i]) 87 { 88 int g=goal[i],dd=dep[g]-dep[nde]; DFS1(g); 89 if(Check(g,nde,dd)) c[nde]=c[g]+dd,bel[nde]=bel[g]; 90 } 91 } 92 void DFS2(int nde,int lst) 93 { 94 int dd=dep[nde]-dep[lst]; 95 if(lst&&Check(lst,nde,dd)) 96 c[nde]=c[lst]+dd,bel[nde]=bel[lst]; 97 for(int i=p[nde];i;i=noww[i]) 98 DFS2(goal[i],nde),d[nde]+=d[goal[i]]; 99 if(!lst) ans[bel[nde]]+=n-d[nde]; 100 else if(bel[nde]!=bel[lst]) 101 { 102 int cut=c[nde]+c[lst]+dd,chk=cut%2||bel[nde]<bel[lst],tmp; 103 tmp=Upt(nde,cut/2-c[nde]-(chk^1)); 104 ans[bel[nde]]+=siz[nde]-d[nde]+tmp,d[nde]=siz[nde]+tmp; 105 } 106 } 107 void Clear(int nde) 108 { 109 for(int i=p[nde];i;i=noww[i]) 110 Clear(goal[i]); 111 bel[nde]=p[nde]=c[nde]=d[nde]=0; 112 } 113 int main() 114 { 115 scanf("%d",&n); 116 for(int i=1;i<n;i++) 117 scanf("%d%d",&t1,&t2),Link(t1,t2),Link(t2,t1); 118 DFS(1,0,1),Calc(1,0),memset(p,0,sizeof p); 119 scanf("%d",&T); 120 while(T--) 121 { 122 scanf("%d",&m),cnt=top=0; 123 for(int i=1;i<=m;i++) scanf("%d",&a[i]),b[i]=a[i]; 124 sort(a+1,a+1+m,cmp); stk[top=1]=a[1],bel[a[1]]=a[1]; 125 for(int i=2;i<=m;i++) Insert(a[i]),bel[a[i]]=a[i]; 126 while(top>1) Link(stk[top-1],stk[top]),top--; 127 DFS1(stk[1]),DFS2(stk[1],0); 128 for(int i=1;i<=m;i++) 129 printf("%d ",ans[b[i]]),ans[b[i]]=0; 130 Clear(stk[1]),puts(""); 131 } 132 return 0; 133 }