xi
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+999; 4 int fa[N][24]; 5 vector<int> v[N]; 6 int n; 7 void ad(int x,int y){ 8 v[x].push_back(y); 9 v[y].push_back(x); 10 } 11 int dep[N],siz[N],zson[N][24],ch[N]; 12 void dfs(int fath,int x){ 13 dep[x]=dep[fath]+1; 14 fa[x][0]=fath; 15 siz[x]=1; 16 zson[x][0]=-1; 17 int maxer=0; 18 for(int i=0;i<v[x].size();i++){ 19 int dot=v[x][i]; 20 if(dot!=fath){ 21 dfs(x,dot); 22 ch[x]+=ch[dot]+siz[dot]; 23 siz[x]+=siz[dot]; 24 if(maxer<siz[dot]){maxer=siz[dot];zson[x][0]=dot;} 25 } 26 } 27 } 28 long long ssiz[N]; 29 void dfs2(int fath,int x){ 30 ssiz[x]=siz[x]+ssiz[fath]; 31 for(int i=0;i<v[x].size();i++){ 32 int dot=v[x][i]; 33 if(dot!=fath){ 34 dfs2(x,dot); 35 } 36 } 37 } 38 int lca(int x,int y){ 39 if(x==y)return x; 40 if(dep[x]<dep[y])swap(x,y); 41 // X 42 for(int i=20;i>=0;i--) 43 if(dep[x]-(1<<i)>=dep[y])x=fa[x][i]; 44 if(x==y)return x; 45 if(dep[y]==1)return y; 46 for(int i=20;i>=0;i--) 47 if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];} 48 return fa[x][0]; 49 } 50 int q,root; 51 int as,qz[200]; 52 int main(){ 53 // freopen("p.in","r",stdin); 54 // freopen("p.out","w",stdout); 55 scanf("%d",&n); 56 for(int i=2;i<=n;i++){ 57 int a,b; 58 scanf("%d",&b); 59 ad(i,b); 60 } 61 dfs(0,1); 62 dfs2(0,1); 63 for(int i=1;i<=20;i++) 64 for(int j=1;j<=n;j++) 65 fa[j][i]=fa[fa[j][i-1]][i-1]; 66 for(int i=1;i<=20;i++) 67 for(int j=1;j<=n;j++) 68 zson[j][i]=zson[zson[j][i-1]][i-1]; 69 cin>>q; 70 71 for(int i=1;i<=q;i++){ 72 long long ans=0; 73 int x,y,dist,all; 74 scanf("%d%d",&x,&y); 75 if(siz[x]<siz[y])swap(x,y); 76 ans=ch[x]; 77 all=siz[x]; 78 if(lca(x,y)!=x){ 79 dist=dep[x]+dep[y]-2; 80 dist-=2*(dep[lca(x,y)]-1); 81 ans+=ch[y]+siz[y]*dist; 82 all+=siz[y]; 83 } 84 int az=x; 85 for(int i=20;i>=0;i--){ 86 int dot=zson[az][i]; 87 if(siz[dot]*2>=all){ 88 ans+=(all<<i)-2*(ssiz[dot]-ssiz[az]); 89 az=dot; 90 } 91 } 92 printf("%d ",ans); 93 } 94 return 0; 95 }