题目
题目描述
世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述：世界树中有 $n$ 个种族，种族的编号分别从 $1$ 到 $n$，分别生活在编号为 $1$ 到 $n$ 的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为 $1$。保证连接的方式会形成一棵树结构，即所有的聚居地之间可以互相到达，并且不会出现环。定义两个聚居地之间的距离为连接他们的道路的长度；例如，若聚居地 $a$ 和 $b$ 之间有道路，$b$ 和 $c$ 之间有道路，因为每条道路长度为 $1$ 而且又不可能出现环，所以 $a$ 与 $c$ 之间的距离为 $2$。
出于对公平的考虑，第 $i$ 年，世界树的国王需要授权 $m_i$ 个种族的聚居地为临时议事处。对于某个种族 $x$（$x$ 为种族的编号），如果距离该种族最近的临时议事处为 $y$（$y$ 为议事处所在聚居地的编号），则种族 $x$ 将接受 $y$ 议事处的管辖（如果有多个临时议事处到该聚居地的距离一样，则 $y$ 为其中编号最小的临时议事处）。
现在国王想知道，在 $q$ 年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。
输入输出格式
输入格式：
第一行为一个正整数n，表示世界树中种族的个数。接下来n-l行，每行两个正整数x，y，表示x聚居地与y聚居地之间有一条长度为1的双向道路。接下来一行为一个正整数q，表示国王询问的年数。接下来q块，每块两行：第i块的第一行为1个正整数m[i]，表示第i年授权的临时议事处的个数。第i块的第二行为m[i]个正整数h[l]、h[2]、…、h[m[i]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。
输出格式：
输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。
输入输出样例
输入样例#1：
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
5
2
6 1
5
2 7 3 6 9
1
8
4
8 7 10 3
5
2 9 3 5 8
输出样例#1：
1 9
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1
说明
N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
题解
因为$\sum_{i=1}^{q} m\le 300000$，考虑建立虚树来求答案
根据钦定点建出虚树来，先要处理出来虚树上每个点的管辖点$ct_x$
因为每个点可能会受ta的兄弟的管辖，所以先要处理儿子对父亲的影响，再处理父亲对儿子的影响
如果一个点$x$的某个子树里没有虚树点，说明ta的子树里都受$ct_x$管辖，所以答案$+siz_{son_x}$
如果一个点$x$的子树里有虚树点$y$，即虚树上$x,y$之间有连边，分类讨论
- 如果$ct_x=ct_y$，说明这条虚树边上的点（不包括$x,y$）的子树都受$ct_x$管辖，所以答案$+(siz_{son_x}-siz_y)$
- 如果$ct_x \not= ct_y$，说明这条虚树边上的点被分成了两部分，分别受$ct_x,ct_y$管辖，这时只需要用倍增找到这个分界点$t$即可，$ct_x$答案$+(siz_{son_x}-siz_t)$，$ct_y$答案$+(siz_t-siz_y)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=3e5+5;
struct p{
int x,y;
}c[MAX<<1];
int n,m,num,Top,cnt;
int h[MAX],ans[MAX],ct[MAX],st[MAX],_T[MAX],T[MAX],top[MAX],id[MAX],_siz[MAX],siz[MAX],son[MAX],d[MAX];
int f[23][MAX];
bool cmp(int a,int b) {return id[a]<id[b];}
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
void add(int x,int y)
{
c[++num]=(p){h[x],y},h[x]=num;
c[++num]=(p){h[y],x},h[y]=num;
}
void dfs(int x=1,int fa=0)
{
f[0][x]=fa,d[x]=d[fa]+(siz[x]=1);
for(int i=h[x];i;i=c[i].x)
if(c[i].y^fa)
{
dfs(c[i].y,x),siz[x]+=siz[c[i].y];
if(siz[c[i].y]>siz[son[x]]) son[x]=c[i].y;
}
}
void dfs1(int x=1,int tp=1)
{
top[x]=tp,id[x]=++cnt;
if(!son[x]) return void(h[x]=0);
dfs1(son[x],tp);
for(int i=h[x];i;i=c[i].x)
if((son[x]^c[i].y)&&(f[0][x]^c[i].y)) dfs1(c[i].y,c[i].y);
h[x]=0;
}
int LCA(int x,int y)
{
while(top[x]^top[y])
{
if(d[top[x]]<d[top[y]]) swap(x,y);
x=f[0][top[x]];
}
return d[x]>d[y]?y:x;
}
void Init()
{
for(int i=1;i<=22;++i)
for(int j=1;j<=n;++j)
f[i][j]=f[i-1][f[i-1][j]];
}
int GET_DIS(int x,int y) {return d[x]+d[y]-(d[LCA(x,y)]<<1);}
int GET_SON(int x,int y)
{
for(int i=22;i>=0;--i)
if(d[f[i][x]]>d[y]) x=f[i][x];
return x;
}
void dfs_(int x=1,int fa=0)
{
ans[x]=0,_siz[x]=siz[x];
for(int i=h[x],_d,__d;i;i=c[i].x)
if(c[i].y^fa)
{
dfs_(c[i].y,x),_d=d[ct[c[i].y]]-d[x],__d=ct[x]?d[ct[x]]-d[x]:1e9;
if(_d<__d||(_d==__d&&ct[x]>ct[c[i].y])) ct[x]=ct[c[i].y];
}
}
void dfs__(int x=1,int fa=0)
{
for(int i=h[x],_d,__d;i;i=c[i].x)
if(c[i].y^fa)
{
_d=GET_DIS(ct[x],c[i].y),__d=GET_DIS(c[i].y,ct[c[i].y]);
if(_d<__d||(_d==__d&&ct[x]<ct[c[i].y])) ct[c[i].y]=ct[x];
dfs__(c[i].y,x);
}
}
void dfs___(int x=1,int fa=0)
{
for(int i=h[x],son,qwq;i;i=c[i].x)
if(c[i].y^fa)
{
dfs___(c[i].y,x),son=GET_SON(c[i].y,x),_siz[x]-=siz[son];
if(ct[c[i].y]==ct[x]) ans[ct[x]]+=siz[son]-siz[c[i].y];
else
{
qwq=c[i].y;
for(int j=22,_d,__d;j>=0;--j)if(f[j][qwq]){_d=GET_DIS(f[j][qwq],ct[x]),__d=GET_DIS(f[j][qwq],ct[c[i].y]);if(_d>__d||(_d==__d&&ct[c[i].y]<ct[x])) qwq=f[j][qwq];}
ans[ct[c[i].y]]+=siz[qwq]-siz[c[i].y],ans[ct[x]]+=siz[son]-siz[qwq];
}
}
h[x]=0,ans[ct[x]]+=_siz[x];
}
void Work(int k)
{
num=0,st[Top=1]=1;
for(int i=1,lca;i<=k;++i)
{
lca=LCA(T[i],st[Top]);
while(Top>1&&d[st[Top-1]]>d[lca]) add(st[Top],st[Top-1]),--Top;
while(Top&&d[lca]<d[st[Top]]) add(st[Top],lca),--Top;
if(!Top||d[st[Top]]<d[lca]) st[++Top]=lca;
if(st[Top]!=T[i]) st[++Top]=T[i];
}
while(Top>1) add(st[Top],st[Top-1]),--Top;
dfs_(),dfs__(),dfs___();
for(int i=1;i<=k;++i)
printf("%d ",ans[_T[i]]);
printf("\n");
}
int main()
{
n=read();
for(int i=1,x;i<n;++i)
x=read(),add(x,read());
dfs(),dfs1(),Init(),m=read();
for(int i=1,k;i<=m;++i)
{
k=read(),memset(ct,0,sizeof(ct));
for(int j=1;j<=k;++j)
T[j]=read(),ct[T[j]]=T[j];
memcpy(_T,T,sizeof(T)),sort(T+1,T+1+k,cmp),Work(k);
}
return 0;
}
