世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。 世界树的形态可以用一个数学模型来描述：世界树中有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]的临时议事处管理的种族个数。
N<=300000, q<=300000,m[1]+m[2]+…+m[q]<=300000
题解：虚树+树形DP+LCA
建立虚树后，我们考虑每条边上的归属。对于每个点我们维护一个离他最近的是临时议事处的点belong。
对于一条边来说，我们先假设可以计算他对于每个点的贡献，那么贡献一定属于他端点维护的临时议事处。
那么对于每个点来说，如何维护belong呢？首先我们先用儿子更新父亲，然后再用父亲更新儿子。临时议事处的belong初始时等于他本身。
先只考虑边上的点(不包括端点)
如果一条边的两个端点的belong相等，那么这条边上所有点(包括这些点的子树，但是如果他的儿子是虚树中的点就不要计算)都给belong
如果belong不相等，那么我们就将这条边二分，注意不是边的长度二分，而是计算上到belong的距离，然后再二分。就是让每个点都能正确的累加到对应的节点上。
我们再考虑虚树中的每个点，那么对于点来说，他有可能有一些儿子没有出现在虚树中，那么这些点(就是除去那些包含虚树中节点的儿子的size，剩下的点)都归这个点的belong。总之细节非常的多。。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 300003 #define inf 1000000000 using namespace std; int m,n,k,tot,sz,point[N],v[N*2],nxt[N*2],c[N*2],deep[N],pos[N],size[N],tp[N],ans[N]; int len[N][23],fa[N][23],mi[N],mark[N],a[N],st[N],top,sk[N],pre,tt,belong[N],b[N]; void add(int x,int y) { tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; } void dfs(int x,int f) { pos[x]=++sz; deep[x]=deep[f]+1; size[x]=1; for (int i=1;i<=20;i++) { if (deep[x]-mi[i]<0) break; fa[x][i]=fa[fa[x][i-1]][i-1]; len[x][i]=len[x][i-1]+len[fa[x][i-1]][i-1]; } for (int i=point[x];i;i=nxt[i]){ if (v[i]==f) continue; len[v[i]][0]=1; fa[v[i]][0]=x; dfs(v[i],x); size[x]+=size[v[i]]; } } int lca(int x,int y,int opt) { if (x==0||y==0) return inf; if (deep[x]<deep[y]) swap(x,y); int k=deep[x]-deep[y]; int sum=0; for (int i=0;i<=20;i++) if ((k>>i)&1) sum+=len[x][i],x=fa[x][i]; if (x==y) if (opt==1) return y; else return sum; for (int i=20;i>=0;i--) if (fa[x][i]!=fa[y][i]) { sum+=len[x][i]; sum+=len[y][i]; x=fa[x][i]; y=fa[y][i]; } sum+=len[x][0]; sum+=len[y][0]; x=fa[x][0]; y=fa[y][0]; if (opt==1) return x; else return sum; } int cmp(int x,int y){ return pos[x]<pos[y]; } int getson(int x,int k) { if (k<=0) return x; for (int i=0;i<=19;i++) if ((k>>i)&1) x=fa[x][i]; return x; } void build(int x,int y) { if (x==y) return; tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=lca(x,y,0); tp[tot]=getson(y,deep[y]-deep[x]-1); //cout<<x<<" "<<y<<" "<<c[tot]<<" "<<tp[tot]<<endl; } void dp(int x) { sk[x]=size[x]; st[++tt]=x; for (int i=point[x];i;i=nxt[i]){ dp(v[i]); sk[x]-=size[tp[i]]; if (!belong[v[i]]) continue; int t1=lca(belong[v[i]],x,0); int t2=lca(belong[x],x,0); if (t1<t2||!belong[x]||t1==t2&&belong[v[i]]<belong[x]) belong[x]=belong[v[i]]; } } void dp1(int x) { for (int i=point[x];i;i=nxt[i]) { if (belong[x]) { int t1=lca(belong[v[i]],v[i],0); int t2=lca(v[i],belong[x],0); if (t2<t1||!belong[v[i]]||t1==t2&&belong[x]<belong[v[i]]) belong[v[i]]=belong[x]; } dp1(v[i]); } } void calc(int x,int y,int c,int tp) { if (c==1) return; if (belong[x]==belong[y]) { int k=deep[y]-deep[x]-1; int x1=y; for (int i=0;i<=19;i++) if ((k>>i)&1) x1=fa[x1][i]; ans[belong[x]]+=size[x1]-size[y]; return; } int t1=lca(belong[x],x,0); int t2=lca(belong[y],y,0); int len=t1+t2+c; int k=len/2; int a=belong[y]; if (k*2==len) { if (belong[y]>belong[x]) k--; } for (int i=0;i<=19;i++) if ((k>>i)&1) a=fa[a][i]; ans[belong[y]]+=size[a]-size[y]; ans[belong[x]]+=size[tp]-size[a]; } void solve() { scanf("%d",&k); for (int i=1;i<=k;i++) scanf("%d",&a[i]),mark[a[i]]=1; for (int i=1;i<=k;i++) belong[a[i]]=a[i],b[i]=a[i]; sort(a+1,a+k+1,cmp); tot=0; tt=0; st[++tt]=1; for (int i=1;i<=k;i++) { int now=a[i]; int f=lca(st[tt],a[i],1); while (true) { if (deep[f]>=deep[st[tt-1]]) { build(f,st[tt--]); if (f!=st[tt]) st[++tt]=f; break; } build(st[tt-1],st[tt]); tt--; } if (now!=st[tt]) st[++tt]=now; } while (tt-1) build(st[tt-1],st[tt]),tt--; tt=0; dp(1); dp1(1); for (int i=1;i<=tt;i++) { for (int j=point[st[i]];j;j=nxt[j]) calc(st[i],v[j],c[j],tp[j]); ans[belong[st[i]]]+=sk[st[i]]; } for (int i=1;i<=k;i++) printf("%d ",ans[b[i]]); printf("\n"); for (int i=1;i<=tt;i++) sk[st[i]]=0,mark[st[i]]=0,point[st[i]]=0,belong[st[i]]=0,ans[st[i]]=0; } int main() { freopen("a.in","r",stdin); freopen("my.out","w",stdout); scanf("%d",&n); for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); } mi[0]=1; for (int i=1;i<=20;i++) mi[i]=mi[i-1]*2; dfs(1,0); scanf("%d",&m); tot=0; memset(point,0,sizeof(point)); for (int i=1;i<=m;i++) solve(); }
