我是什么时候写的这题的qwq
首先,发现关键点的总数被限制了,很自然想到虚树,并且,对于一个关键点,他管理的点显然是一个联通块
然后把虚树先建出来,然后两次dfs,第一次是向祖先更新离每个点最近的关键点是哪个,然后第二次向子树更新,这样就能得到每个虚树上的点属于哪个集合
然后还要考虑不在虚树上的点的贡献.如果虚树上一条边,两端点属于同一集合,那么这条边上不在虚树上的点都是那个集合的;否则就有下面一半点属于下面,上面一半点属于上面.倍增找到分界点,然后更新答案即可
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=3e5+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int eto[N<<1],ent[N<<1],ehd[N],et=1;
il void edd(int x,int y)
{
++et,eto[et]=y,ent[et]=ehd[x],ehd[x]=et;
++et,eto[et]=x,ent[et]=ehd[y],ehd[y]=et;
}
int n,l2n;
int fa[N][20],de[N],sz[N],dfn[N],ti;
void init(int x)
{
sz[x]=1,dfn[x]=++ti;
for(int j=1;j<=l2n;++j) fa[x][j]=fa[fa[x][j-1]][j-1];
for(int i=ehd[x];i;i=ent[i])
{
int y=eto[i];
if(y==fa[x][0]) continue;
fa[y][0]=x,de[y]=de[x]+1,init(y),sz[x]+=sz[y];
}
}
il int glca(int x,int y)
{
if(x==y) return x;
if(de[x]<de[y]) swap(x,y);
for(int j=l2n;~j;--j) if(de[fa[x][j]]>=de[y]) x=fa[x][j];
if(x==y) return x;
for(int j=l2n;~j;--j) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];
return fa[x][0];
}
il int jmp(int x,int y)
{
for(int j=l2n;~j;--j) if(de[fa[x][j]]>de[y]) x=fa[x][j];
return x;
}
int to[N],nt[N],hd[N],tot;
il void add(int x,int y)
{
++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot;
}
int st[N],tp,ss[N],ts,a[N],b[N],ta,di[N],be[N],an[N];
il bool cmp(int a,int b){return dfn[a]<dfn[b];}
il void buiitr()
{
for(int i=1;i<=ts;++i) hd[ss[i]]=0;
ts=tp=0,tot=0;
ta=rd()+1;a[1]=1;
for(int i=2;i<=ta;++i) a[i]=b[i-1]=rd();
sort(a+2,a+ta+1,cmp);
ss[++ts]=st[++tp]=1,be[1]=1,di[1]=0;
for(int i=2+(a[2]==1);i<=ta;++i)
{
int x=a[i];
if(tp==1) ss[++ts]=st[++tp]=x,di[x]=0,be[x]=x;
else
{
int lca=glca(x,st[tp]);
if(st[tp]!=lca)
{
while(dfn[st[tp-1]]>dfn[lca]) add(st[tp-1],st[tp]),--tp;
add(lca,st[tp]),--tp;
if(st[tp]!=lca) ss[++ts]=st[++tp]=lca,di[lca]=n+1,be[lca]=0;
}
ss[++ts]=st[++tp]=x,di[x]=0,be[x]=x;
}
}
while(tp>1) add(st[tp-1],st[tp]),--tp;
}
void dfs1(int x)
{
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
dfs1(y);
if(di[x]>di[y]+de[y]-de[x]||(di[x]==di[y]+de[y]-de[x]&&be[x]>be[y]))
di[x]=di[y]+de[y]-de[x],be[x]=be[y];
}
}
void dfs2(int x)
{
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(di[y]>di[x]+de[y]-de[x]||(di[y]==di[x]+de[y]-de[x]&&be[y]>be[x]))
di[y]=di[x]+de[y]-de[x],be[y]=be[x];
dfs2(y);
}
}
void dfs3(int x)
{
int cn=sz[x];
for(int i=hd[x];i;i=nt[i])
{
int y=to[i],yy=jmp(y,x);
cn-=sz[yy];
if(be[x]==be[y]) cn+=sz[yy]-sz[y];
else
{
int nw=y;
for(int j=l2n;~j;--j)
if(de[y]-de[fa[nw][j]]+di[y]<de[fa[nw][j]]-de[x]+di[x]||(de[y]-de[fa[nw][j]]+di[y]==de[fa[nw][j]]-de[x]+di[x]&&be[y]<be[x])) nw=fa[nw][j];
cn+=sz[yy]-sz[nw],an[be[y]]+=sz[nw]-sz[y];
}
dfs3(y);
}
an[be[x]]+=cn;
}
int main()
{
n=rd();l2n=log2(n);
for(int i=1;i<n;++i) edd(rd(),rd());
init(1);
int q=rd();
de[0]=-n;
while(q--)
{
buiitr();
if(a[2]>1) be[1]=0,di[1]=n+1;
dfs1(1),dfs2(1),dfs3(1);
for(int i=1;i<ta;++i) printf("%d ",an[b[i]]),an[b[i]]=0;
putchar('
');
}
return 0;
}