Hnoi2014 世界树
Description
世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。
世界树的形态可以用一个数学模型来描述：世界树中有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年的时间里，每一年完成授权后，当年每个临时议事处将会管理多少个种族（议事处所在的聚居地也将接受该议事处管理）。 现在这个任务交给了以智慧著称的灵长类的你：程序猿。请帮国王完成这个任务吧。
Input
第一行为一个正整数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]]，表示被授权为临时议事处的聚居地编号（保证互不相同）。
Output
输出包含q行，第i行为m[i]个整数，该行的第j(j=1，2…，，m[i])个数表示第i年被授权的聚居地h[j]的临时议事处管理的种族个数。
Sample Input
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
Sample Output
3 1 4 1 1
10
1 1 3 5
4 1 3 1 1
HINT
N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
这道题知道用虚树后再乱搞即可。
我觉得代码思路还是很清晰的，直接看也看得懂。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
const int INF=;
int cntE,fir[maxn],to[maxn*],nxt[maxn*]; void addedge(int a,int b){
nxt[++cntE]=fir[a];
fir[a]=cntE;
to[cntE]=b;
} int fa[maxn][],dep[maxn];
int sz[maxn],son[maxn];
void DFS(int x){
sz[x]=;
for(int k=;
(fa[x][k+]=fa[fa[x][k]][k]);
k++);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x][]){
fa[to[i]][]=x;
dep[to[i]]=dep[x]+;
DFS(to[i]);
sz[x]+=sz[to[i]];
if(sz[to[i]]>sz[son[x]])
son[x]=to[i];
}
} int rID[maxn],tot;
int top[maxn],ID[maxn]; void DFS(int x,int tp){
top[x]=tp;
ID[x]=++tot;rID[tot]=x;
if(son[x])DFS(son[x],tp);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x][]&&to[i]!=son[x])
DFS(to[i],to[i]);
} int Lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])
swap(x,y);
x=fa[top[x]][];
}
if(dep[x]<dep[y])
swap(x,y);
return y;
} int Get(int y,int d){
while(dep[top[y]]>d)
y=fa[top[y]][];
int dis=dep[y]-d;
for(int i=;i>=;i--)
if(dis>>i&)y=fa[y][i];
return y;
} pair<int,int>g[maxn];
int h[maxn],mem[maxn];
int ans[maxn],t[maxn];
int st[maxn],pre[maxn],val[maxn];
int n,m,Q,tp;
int main(){
#ifndef ONLINE_JUDGE
freopen("worldtree.in","r",stdin);
freopen("worldtree.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
dep[]=;
DFS();DFS(,);
scanf("%d",&Q);
while(Q--){
scanf("%d",&m);tot=;
for(int i=;i<=m;i++){
scanf("%d",&h[i]);mem[i]=h[i];
g[h[i]]=make_pair(,h[i]);
ans[h[i]]=;h[i]=ID[h[i]];
t[++tot]=h[i];
}
sort(h,h+m+);tp=;
for(int i=;i<=m;i++)
h[i]=rID[h[i]];
for(int i=;i<=m;i++){
if(i==)
pre[st[++tp]=h[i]]=;
else{
int p=h[i],lca=Lca(p,st[tp]);
for(;dep[st[tp]]>dep[lca];tp--)
if(dep[st[tp-]]<=dep[lca])
pre[st[tp]]=lca;
if(st[tp]!=lca){
t[++tot]=ID[lca];
g[lca]=make_pair(INF,);
pre[lca]=st[tp];
st[++tp]=lca;
}
pre[p]=st[tp];
st[++tp]=p;
}
}
sort(t+,t+tot+);
for(int i=;i<=tot;i++)
t[i]=rID[t[i]];
for(int i=;i<=tot;i++){
int p=t[i],f=pre[p];
if(i==)val[p]=n;
else{
val[p]=sz[p];
val[f]-=sz[Get(p,dep[f]+)];
}
}
for(int i=tot;i>;i--){
int p=t[i],f=pre[p],w=dep[p]-dep[f];
g[f]=min(g[f],make_pair(g[p].first+w,g[p].second));
}
for(int i=;i<=tot;i++){
int p=t[i],f=pre[p],w=dep[p]-dep[f];
g[p]=min(g[p],make_pair(g[f].first+w,g[f].second));
}
ans[g[t[]].second]+=val[t[]];
for(int i=;i<=tot;i++){
int p=t[i],f=pre[p];
ans[g[p].second]+=val[p];
if(g[p].second==g[f].second)
ans[g[p].second]+=sz[Get(p,dep[f]+)]-sz[p];
else{
int da=dep[f],db=dep[p],mid;
if(g[f].first>g[p].first)
db-=g[f].first-g[p].first;
if(g[f].first<g[p].first)
da+=g[p].first-g[f].first;
mid=(da+db+)/;
mid+=((db-da)%==&&g[f].second<g[p].second)?:;
int q=Get(p,mid);
ans[g[p].second]+=sz[q]-sz[p];
ans[g[f].second]+=sz[Get(p,dep[f]+)]-sz[q];
}
}
for(int i=;i<=m;i++){
printf("%d ",ans[mem[i]]);
ans[mem[i]]=;
}
printf("\n");
}
return ;
}