JZOJ 4639 Angel Beats!【NOIP提高组A组7.16】

#Angel Beats!

##题目大意

给你一棵1为根的树，然后会有q个询问，向你查询点x子树和点y子树的重心，重心可能会有很多个，你只需要输出距离和即可。

两棵子树的重心的定义如下：在树上找到一个点，使得该点到两棵子树中所有点距离之和最小，即这两棵子树的重心。

##输入格式

第一行一个整数 ，代表点的数量。

接下来 n-1行，第i 行的表示节点i 的父亲节点。

接下来一个整数q ，为询问的个数。

接下来q 行，每行两个数x,y ，表示查询子树x 和子树y 的重心，输出这个点到两颗子树中所有点距离之和。

##输出格式

输出有q行，每行一个整数，表示你求得的距离。

##样例输入

9

1

2

3

3

7

2

7

1

3

3 7

3 2

7 9

##样例输出

10

10

5

##样例解释

##数据范围

##题解

首先预处理出以每个点为根节点时对应的子树大小，以及所有的点到每个点的距离和。

（方法很简单，把整棵树遍历一次即可，做法略，请读者自行思考）

我们同时也要预处理出以每个点为根节点对应的子树的重心。

先给出重心的定义和性质。

定义：以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树大小的一半。

性质：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。

至于找重心，可以这样做。

假设我们要找以点 v v v为根节点的子树的重心，那么它的重心一定在点 o o o最大的子树的重心到点 o o o的路径上（显然，证明略，请读者自行思考），我们可以用倍增算法去找，同时，我们找出来的点深度越大越好。（很***显然***，这个点的深度越大，这棵子树里的所有点到此点的距离和越小，证明略，请读者自行思考）

对于一个在以 y y y为根的子树内的点 x x x， 子树里的所有点到点 x x x的距离和可以这么求，我们正难则反：

子树所有点到x距离和

=所有点到x距离和-非子树所有点到x距离和

=所有点到x距离和-非子树所有点到子树根距离和-(n-子树大小)× dist(x, y)

=所有点到x距离和-（所有点到子树根距离和-子树所有点到子树根距离和）-(n-子树大小)× (x的深度-y的深度)

我们发现上面的每一项我们都可以 O n O_n On​预处理出来。

要做对这道题，我们还需要一些结论：

结论 1：两棵子树的重心一定在两棵子树各自重心连线的路径上。

证明：显然……

结论 2：在两棵子树size较大那棵内部一定能找到两棵子树重心。

证明：如果在树根连线上，一定能调整，越靠近Size较大的子树距离和越小，所以重心在那棵Size较大的子树内部，其中Size指子树的大小。（点数的多少）

我们一样用倍增算法在Size较大的子树的重心到其根节点的路径中找两棵子树的重心，深度一样是越深越好。

求出重心后，用预处理出来的信息经过一系列运算后便可算出答案（计算过程略，请读者自行思考）。

还有一点，算出答案我们还需要求出对于每个询问中的 x x x与 y y y的路径所经过的边数，一样用倍增求就可以了。

好吧，还有一点，如果点y在点x为根的子树内，或点x在点y为根的子树内，这种情况分开讨论即可。

##Code(Pascal)

label 123;constjx=18;varn,i,j,k,o,l,p,x,y,jgd,cqy,kkk,op,dis,ans,q,zd,zgdx:longint;bz:array[0..101000,0..jx] of longint;fa,size,zx,en,sd,jd,kd:array[0..101000] of longint;bj:array[0..101000,1..2] of longint;procedure qsort(l,r:longint);vari,j,m:longint;begini:=l;j:=r;m:=bj[(l+r) div 2,1];repeatwhile bj[i,1]<m do inc(i);while bj[j,1]>m do dec(j);if i<=j thenbeginbj[0]:=bj[i];bj[i]:=bj[j];bj[j]:=bj[0];inc(i);dec(j);end;until i>j;if l<j then qsort(l,j);if i<r then qsort(i,r);end;procedure dg(O:longint);varl,i:longint;beginl:=0;bz[o,l]:=fa[o];while bz[bz[o,l],l]>0 dobeginbz[o,l+1]:=bz[bz[o,l],l];inc(l);end;for i:=en[o-1]+1 to en[o] dobeginsd[bj[i,2]]:=sd[o]+1;dg(bj[i,2]);jd[o]:=jd[bj[i,2]]+jd[o]+size[bj[i,2]];size[o]:=size[bj[i,2]]+size[o];end;inc(size[o]);end;procedure bl(o:longint);vari:longint;beginfor i:=en[o-1]+1 to en[o] dobeginkd[bj[i,2]]:=kd[o]-size[bj[i,2]]+(n-size[bj[i,2]]);bl(bj[i,2]);end;end;procedure zzx(o:longint);vari,ms,u,uuu:longint;beginms:=0;for i:=en[o-1]+1 to en[o] dobeginzzx(bj[i,2]);if size[bj[i,2]]>size[ms] then ms:=bj[i,2];end;if o=1 theno:=1;if ms=0 thenbeginzx[o]:=o;exit;end;if size[ms]<=size[o]-size[ms] then zx[o]:=oelsebeginu:=zx[ms];l:=jx;uuu:=size[o];while l>=0 dobeginif (sd[bz[u,l]]>=sd[o]) and (uuu-size[bz[u,l]]>uuu div 2) thenu:=bz[u,l];dec(l);end;while uuu-size[u]>uuu div 2 do u:=fa[u];zx[o]:=u;end;end;function xz(a,b:longint):longint;vari,j,k:longint;begink:=jx;if sd[a]>sd[b] thenwhile k>=0 dobeginif sd[bz[a,k]]>=sd[b] then a:=bz[a,k];dec(k);endelsewhile k>=0 dobeginif sd[bz[b,k]]>=sd[a] then b:=bz[b,k];dec(k);end;k:=jx;while k>=0 dobeginif sd[bz[a,k]]<>sd[bz[b,k]] thenbegina:=bz[a,k];b:=bz[b,k];end;dec(k);end;while a<>b dobegina:=fa[a];b:=fa[b];end;exit(a);end;beginreadln(n);size[0]:=maxlongint;for i:=2 to n dobeginreadln(fa[i]);inc(en[fa[i]]);bj[i-1,1]:=fa[i];bj[i-1,2]:=i;end;for i:=1 to n doen[i]:=en[i-1]+en[i];sd[1]:=1;qsort(1,n-1);dg(1);kd[1]:=jd[1];bl(1);size[0]:=0;zzx(1);size[0]:=maxlongint;readln(q);for i:=1 to q dobeginreadln(x,y);zd:=xz(x,y);if (zd=x) or (zd=y) thenbegincqy:=zx[zd];op:=zd;dis:=sd[cqy]-sd[op];ans:=kd[cqy]-(kd[op]-jd[op])-(n-size[op])*dis;goto 123;end;zd:=sd[zd];jgd:=sd[x]-zd+sd[y]-zd-1;if size[x]>=size[y] thenbeginop:=x;cqy:=zx[x];endelsebeginop:=y;cqy:=zx[y];end;kkk:=jx;zgdx:=size[x]+size[y];while kkk>=0 dobeginif (zgdx-size[bz[cqy,kkk]]>zgdx div 2) and(sd[bz[cqy,kkk]]>=sd[op]) then cqy:=bz[cqy,kkk];dec(kkk);end;while zgdx-size[cqy]>zgdx div 2 do cqy:=fa[cqy];dis:=sd[cqy]-sd[op];ans:=kd[cqy]-(kd[op]-jd[op])-(n-size[op])*dis;ans:=ans+jd[x+y-op]+size[x+y-op]*(jgd+1+dis);123:writeln(ans);end;end.