# 题解 CF1806E Tree Master()-其他

## 题解 CF1806E Tree Master()

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005,maxsq=410;
int a[maxn],f[maxn],dp[maxn];
int CNT[maxn],NUM[maxn];
int sum[maxn],vis[maxn],az[maxn],za;
long long Ans[maxn][maxsq];
long long GetAns(int x,int y){
long long re=0;
while(x&&!Ans[x][vis[y]]){
re+=1ll*a[x]*a[y];
x=f[x];y=f[y];
}
return re+Ans[x][vis[y]];
}
bool cmp(int x,int y){
return dp[x]==dp[y]?vis[x]<vis[y]:dp[x]<dp[y];
}
int main(){
// freopen("test.in","r",stdin);
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
++CNT[dp[1]=1];NUM[1]=1;
for(int i=2;i<=n;++i){
scanf("%d",&f[i]);
dp[i]=dp[f[i]]+1;
++CNT[dp[i]];
}
int tmp=400;
for(int i=n;i>=1;--i){
if(CNT[dp[i]]<=tmp||vis[i]){
vis[f[i]]=vis[i]=true;
}
}
for(int i=1;i<=n;++i){
if(vis[i]){
vis[i]=++sum[dp[i]];
az[++za]=i;
}
}
sort(az+1,az+za+1,cmp);
for(int i=1;i<=za;++i){
int u=az[i];
for(int j=i;j<=za&&dp[az[i]]==dp[az[j]];++j){
int v=az[j];
Ans[u][vis[v]]=Ans[v][vis[u]]=1ll*a[u]*a[v]+Ans[f[u]][vis[f[v]]];
}
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",GetAns(x,y));
}
return 0;
}

————————

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005,maxsq=410;
int a[maxn],f[maxn],dp[maxn];
int CNT[maxn],NUM[maxn];
int sum[maxn],vis[maxn],az[maxn],za;
long long Ans[maxn][maxsq];
long long GetAns(int x,int y){
long long re=0;
while(x&&!Ans[x][vis[y]]){
re+=1ll*a[x]*a[y];
x=f[x];y=f[y];
}
return re+Ans[x][vis[y]];
}
bool cmp(int x,int y){
return dp[x]==dp[y]?vis[x]<vis[y]:dp[x]<dp[y];
}
int main(){
// freopen("test.in","r",stdin);
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
++CNT[dp[1]=1];NUM[1]=1;
for(int i=2;i<=n;++i){
scanf("%d",&f[i]);
dp[i]=dp[f[i]]+1;
++CNT[dp[i]];
}
int tmp=400;
for(int i=n;i>=1;--i){
if(CNT[dp[i]]<=tmp||vis[i]){
vis[f[i]]=vis[i]=true;
}
}
for(int i=1;i<=n;++i){
if(vis[i]){
vis[i]=++sum[dp[i]];
az[++za]=i;
}
}
sort(az+1,az+za+1,cmp);
for(int i=1;i<=za;++i){
int u=az[i];
for(int j=i;j<=za&&dp[az[i]]==dp[az[j]];++j){
int v=az[j];
Ans[u][vis[v]]=Ans[v][vis[u]]=1ll*a[u]*a[v]+Ans[f[u]][vis[f[v]]];
}
}
while(q--){
int x,y;
scanf("%d%d",&x,&y);
printf("%lld\n",GetAns(x,y));
}
return 0;
}