Description
天使立华奏攻入了死后世界战线（SSS）的地下工会Guild，这是万分危急的时候。仲村由理指挥工会成员有条不紊地进行撤退工作。工会成员在Guild最深层工厂安放炸药需要很长的准备时间，需要有人来拖延立华奏的前进速度。但是他们并不清楚立华奏的具体位置，因此他们需要设立许多个防御点。
Guild的结构可以看成一棵有n 个节点的树，有时由理会得到立华奏的大概位置，可能在某两棵子树的任意一棵中，她就会找到Guild树（不一定要在两棵子树内）上的一个点，使得该点到两棵子树中所有点距离之和最小，即这两棵子树的重心（如果两棵子树有重合部分，那么取它们并集求重心）。
具体而言，你会得到Guild的结构（1为根），然后会有q个询问，向你查询点x子树和点y子树的重心，重心可能会有很多个，你只需要输出距离和即可。
Analysis
2017 5月：光荣入AB，成为伪团长铁粉=w=
crazy大佬的神题！
结论 1：两棵子树的重心一定在两棵子树各自重心连线的路径上。
嗯，感性理解起来是显然的。
结论 2：在两棵子树size较大那棵内部一定能找到两棵子树重心。
还是感性理解。当然，证明是由结论一，让重心在两颗子树的重心连线路径上调整必能更优。
结论 2 的推论：对于一个点x，令其size最大儿子为y，如果size[y]<=size[x]-size[y]，那么子树x的重心一定为x，否则就一定在点y的子树内。
有了这个，直接从重心往上倍增。
疯狂的结论QAQ！
求每个子树的重心，可以用正难则反的思想。
子树所有点到x距离和=所有点到x距离和-非子树所有点到x距离和
维护几个东西，乱搞一下。
然后一棵树重心可能有两个，而我们求的总是较深的那一个，所以另一个重心（此时就是它的父亲）也要拉去讨论一下（好像不这么干会错）
Code
具体的实现细节极极极极多，直追GDOI的疯狂动物城。
我用对拍拍出了至少10个小错误。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,v) for(int i=last[v];i;i=next[i])
using namespace std;
const int N=100010,M=2*N;
int n,tot,to[M],next[M],last[N],f[N][20],dep[N],size[N],sum[N],val[N],focus[N];
void link(int u,int v)
{
to[++tot]=v,next[tot]=last[u],last[u]=tot;
}
void dfs(int v,int from,int d)
{
size[v]=1,dep[v]=d;
efo(i,v)
{
int u=to[i];
if(u==from) continue;
dfs(u,v,d+1);
size[v]+=size[u],sum[v]+=sum[u];
}
sum[v]+=size[v]-1;
}
int getlca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
fd(i,log2(dep[u]),0)
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
fd(i,log2(dep[u]),0)
if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
if(u!=v) return f[u][0];
return u;
}
int dis(int u,int v)
{
return dep[u]+dep[v]-2*dep[getlca(u,v)];
}
int all(int x,int y)
{
if(getlca(x,y)==y) return val[x]-(val[y]-sum[y])-(n-size[y])*dis(x,y);
else return sum[y]+dis(x,y)*size[y];
}
int up(int v,int d,int p)
{
fd(i,log2(dep[v]),0)
if(f[v][i] && dep[f[v][i]]>=d && size[f[v][i]]<p-size[f[v][i]]) v=f[v][i];
return v;
}
void dfs1(int v,int from)
{
int k=0,sum=0;
efo(i,v)
{
int u=to[i];
if(u==from) continue;
val[u]=val[v]-size[u]+n-size[u];
dfs1(u,v);
if(size[u]>size[k]) k=u;
sum+=size[u];
}
if(size[k]<=sum-size[k]) focus[v]=v;
else
{
focus[v]=up(focus[k],dep[v],sum+1);
if(all(f[focus[v]][0],v)<all(focus[v],v)) focus[v]=f[focus[v]][0];
}
}
int main()
{
scanf("%d",&n);
fo(i,2,n)
{
scanf("%d",&f[i][0]);
link(i,f[i][0]),link(f[i][0],i);
}
fo(j,1,log2(n))
fo(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
dfs(1,0,1);
val[1]=sum[1];
dfs1(1,0);
int _,x,y,u;
scanf("%d",&_);
while(_--)
{
scanf("%d %d\n",&x,&y);
int lca=getlca(x,y);
if(x==lca)
{
printf("%d\n",all(focus[x],x));
continue;
}
if(y==lca)
{
printf("%d\n",all(focus[y],y));
continue;
}
int num=size[x]+size[y];
if(size[x]>size[y]) u=up(focus[x],dep[x],num);
else u=up(focus[y],dep[y],num);
printf("%d\n",min(all(u,x)+all(u,y),all(f[u][0],x)+all(f[u][0],y)));
}
return 0;
}