为啥让深度小于 1000 的暴力做否则记搜的复杂度是对的。

#include<bits/stdc++.h>

using namespace std;
 
#define ll long long
#define M 100005 
#define inf 1e18

int n,q;
int p[M];
ll a[M];
vector<int> g[M];

unordered_map<int,ll> dp[M];

ll dfs(int x,int y){
	if(dp[x][y]) return dp[x][y];
	if(x==0&&y==0) return 0;
	return dp[x][y]=dfs(p[x],p[y])+a[x]*a[y];
}

int dep[M];

void dfs2(int u){
	for(auto v:g[u]){
		dep[v]=dep[u]+1;
		dfs2(v);
	}
}

ll dfs3(int x,int y){
	if(x==0&&y==0) return 0;
	return dfs3(p[x],p[y])+a[x]*a[y];
}

int main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
	for(int i=2;i<=n;++i) scanf("%d",&p[i]),g[p[i]].push_back(i);
	dfs2(1);
	int maxn=0;
	for(int i=1;i<=n;++i) maxn=max(maxn,dep[i]);
	int B=1000;
	while(q--){
		int x,y;
		scanf("%d %d",&x,&y);
		if(dep[x]<=B) printf("%lld\n",dfs3(x,y));
		else printf("%lld\n",dfs(x,y));
	}
	return 0;
}