考虑将虚树建出来
我们先对于每个虚树的点点求出被哪个地方支配
然后考虑对每一条边考虑
如果两边点被同一点支配就不用管了
否则考虑倍增找到中点
分别计算一下贡献
可以处理一个表示子树中除去已经被计算过的剩下的
也就可以方便统计那些没有关键点的子树了
具体可以看代码
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
const int N=300005;
int fa[N][22],dep[N],siz[N],rem[N],bel[N],f[N],dfn[N],tim;
int all[N],tot;
int n,q,stk[N],top,idx[N],a[N],vis[N],num;
inline bool comp(int a,int b){
return dfn[a]<dfn[b];
}
inline int Lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;~i;i--)
if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
if(u==v)return u;
for(int i=20;~i;i--)
if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
inline int dist(int u,int v){
return dep[u]+dep[v]-2*dep[Lca(u,v)];
}
struct G{
int adj[N],nxt[N<<1],to[N<<1],cnt;
inline void addedge(int u,int v){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
void dfs1(int u){
siz[u]=1,dfn[u]=++tim;
for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(v==fa[u][0])continue;
dep[v]=dep[u]+1,fa[v][0]=u;
dfs1(v),siz[u]+=siz[v];
}
}
void dfs2(int u){
all[++tot]=u,rem[u]=siz[u];
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
dfs2(v);
if(!bel[v])continue;
int f1=dist(u,bel[u]),f2=dist(u,bel[v]);
if(!bel[u]||(f1>f2)||(f1==f2&&bel[v]<bel[u]))bel[u]=bel[v];
}
}
void dfs3(int u){
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
int f1=dist(v,bel[u]),f2=dist(v,bel[v]);
if(!bel[v]||(f1<f2)||(f1==f2&&(bel[u]<bel[v])))bel[v]=bel[u];
dfs3(v);
}
}
void solve(int u,int v){
int x=v,y=v;
for(int i=20;~i;i--)if(dep[fa[x][i]]>dep[u])x=fa[x][i];
rem[u]-=siz[x];
if(bel[u]==bel[v]){f[bel[u]]+=siz[x]-siz[v];return;}
for(int i=20;~i;i--){
int mid=fa[y][i];
if(dep[mid]<=dep[u])continue;
int f1=dist(mid,bel[u]),f2=dist(mid,bel[v]);
if(f2<f1||(f1==f2&&bel[v]<bel[u]))y=mid;
}
f[bel[u]]+=siz[x]-siz[y],f[bel[v]]+=siz[y]-siz[v];
}
void calc(){
for(int i=1;i<=tot;i++){
int u=all[i];
for(int e=adj[u];e;e=nxt[e])
solve(u,to[e]);
}
for(int i=1;i<=tot;i++)f[bel[all[i]]]+=rem[all[i]];
for(int i=1;i<=num;i++)cout<<f[idx[i]]<<" ";puts("");
}
}G1,G2;
inline void solve(){
stk[top=1]=a[1];
for(int i=2;i<=num;i++){
int lca=Lca(stk[top],a[i]);
while(dfn[lca]<dfn[stk[top]]){
if(dfn[lca]>=dfn[stk[top-1]]){
G2.addedge(lca,stk[top--]);
if(stk[top]!=lca)stk[++top]=lca;
break;
}
G2.addedge(stk[top-1],stk[top]),top--;
}
stk[++top]=a[i];
}
while(top>1)G2.addedge(stk[top-1],stk[top]),top--;
G2.dfs2(stk[1]),G2.dfs3(stk[1]),rem[stk[1]]=siz[1],G2.calc();
for(int i=1;i<=tot;i++){int u=all[i];f[u]=G2.adj[u]=rem[u]=bel[u]=0;}
G2.cnt=tot=0;
}
int main(){
n=read();dep[1]=1;
for(int i=1;i<n;i++){
int u=read(),v=read();
G1.addedge(u,v),G1.addedge(v,u);
}G1.dfs1(1);
q=read();
while(q--){
num=read();
for(int i=1;i<=num;i++)a[i]=read(),vis[a[i]]=1,idx[i]=a[i],bel[a[i]]=a[i];
sort(a+1,a+num+1,comp),solve();
}
}