题目大意
给你一棵树，然后定义一个函数 $ f(x,y) $，接下来给你 $ q $ 组询问 \(x_{i},y_{i}\)，让你求每一次的 $ f(x_{i},y_{i})$。
分析
首先我们尝试根据这个函数的定义暴力求值，代码实现如下。
ll BFquery(int g,int h) {
if(!g) return 0;
return 1ll*a[g]*a[h]+BFquery(p[g],p[h]);
}
每次调用这个函数即可。时间复杂度是 $ O(nq) $,不足以通过此题。
于是我们来分析题目中用粗体标注的一个条件：每次给出的 \(x_{i}\) 和 \(y_{i}\)，它们深度相同。
这就表明一个点的权值只会和与它处于同一深度的任意一个点相乘，这就减少了相乘点对的组数，也增加了它们出现的次数，会导致我们多次计算同一个 \(f(x,y)\) 的值，增大时间复杂度。
对于这个问题，我们可以尝试用类似记忆化搜索的方法来解决，但是为了不超过空间限制，也不能全部记录，即对于每一组 \(x,y\)，我们可以设一个值 \(B\)，即在不记录答案的情况下，最多计算 \(B\) 次。对于余下的计算，每次的值都会被存储在一个 map 中，这样时间复杂度可以优化至近似 \(O(Bq)\)。
而另外一种方法，存储深度较大的部分而不存储深度较小的部分，目前没有找到这方面正确的做法，如果以后找到我会补上。
下面是代码。
int n,q,a[100005]={},p[100005]={},d[100005]={},rp[100005]={},f,s,cnt=0,P;
ll res;
vector<int> v[100005],op[100005];
map<ll,ll> mp;
const int M=100005,B=500;
ll BFquery(int g,int h) {
if(!g) return 0;
if(g>h) swap(g,h);
if(mp[1ll*g*M+h]!=0) return mp[1ll*g*M+h];
else {
mp[1ll*g*M+h]=1ll*a[g]*a[h]+BFquery(p[g],p[h]);
return mp[1ll*g*M+h];
}
}
void wk() {
read(n),read(q);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=2,x;i<=n;++i) {
read(x);
v[x].emplace_back(i);
p[i]=x;
}
while(q--) {
read(f),read(s);
if(f>s) swap(f,s);
res=0;
P=B;
while(f && s && P>0) {
res+=1ll*a[f]*a[s];
f=p[f];
s=p[s];
--P;
}
if(f) res+=BFquery(f,s);
writeln(res);
}
}