2023-07-19 10:59:11
思路来源于题解:https://www.luogu.com.cn/problem/solution/CF1806E
算法：根号分治+记忆化搜索。
因为每一个查询都是同层的，我们可以只记忆层数少的（小于\(\sqrt n\)）,对于层数多的层，如果大于$ \sqrt n\(，那么这种层数的数量肯定小于\) \sqrt n$ ,一共有 \(q\) 次查询，假设每次都查层数多的，那因为层数少的记忆化了可以直接下传看作 \(O(1)\)。
然后上查过程中经过的层数多的只有$ \sqrt n$ 层
复杂度 \(O(q \sqrt n )\) ，而层数少的查询全搜完也只有 $O(n \sqrt n) \(
记忆化数组第一个存编号，第二个存总层编号。
总复杂度\) O(q\ sqrt n + n \sqrt n ) $，可过。
\(Code\)
int n,q,fa[100005],deep[100005],siz[100005],idc[100005];//idc=层id siz=层大小,s=题给f(i,i),f=记忆化数组
ll a[100005],f[100005][318],s[100005];
ll dfs(int x,int y){
if(x==y)return s[x];
if(siz[deep[x]]<=318){
if(f[x][idc[y]])return f[x][idc[y]];
return f[x][idc[y]]=f[y][idc[x]]=dfs(fa[x],fa[y])+a[x]*a[y];
}
return dfs(fa[x],fa[y])+a[x]*a[y];//优雅的暴力
}
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
if(i^1)fa[i]=read();// 因为题给 fa[i]<i,所以可以直接循环不用考虑之前没有更新过
s[i]=s[fa[i]]+a[i]*a[i];
deep[i]=deep[fa[i]]+1;
idc[i]=++siz[deep[i]];//一边更新深度一边更新标号
}
while(q--){
int x=read(),y=read();
printf("%lld\n",dfs(x,y));
}
}