考虑一个最基础的暴力，就是直接记忆化搜索暴力往上跳。
但是能发现如果一层的节点数过多，状态数太多，就寄了。
再考虑一个基础的暴力，就是直接跳。
但是如果要跳的层数过多，就寄了。
考虑结合一下，根号分治。
对于一层内节点数 \(\le \sqrt{n}\) 的记录下每两个点间的答案。
对于节点数 \(> \sqrt{n}\) 的节点暴力往上跳跳到一个已经得到的状态即可。
复杂度证明：
对于状态数，相当于是求 \(\max\{\sum\limits d_i^2\}(\sum\limits d_i = n, d_i\in \mathbb{N})\)，因为有 \(x^2 + y^2 \ge (x + 1)^2 + (y - 1)^2(x < y)\)，所以肯定是当 \(d_i = \sqrt{n}\) 时取到 \(\max\)，值为 \(n\sqrt{n}\)，所以状态数是 \(O(n\sqrt{n})\) 的。
对于 \(> \sqrt{n}\) 的层，最多只会有 \(\sqrt{n}\) 层，就最多会往上跳 \(\sqrt{n}\) 次，复杂度 \(O(q\sqrt{n})\)。
综上，时间复杂度 \(O(n\sqrt{n} + q\sqrt{n})\)。
#include<bits/stdc++.h>
using i64 = long long;
const int maxn = 1e5 + 10, B = 300;
i64 a[maxn];
int fa[maxn], dep[maxn];
std::vector<int> P[maxn];
i64 ans[maxn][B + 10];
int id[maxn];
bool vis[maxn];
inline i64 calc(int x, int y) {
if (vis[dep[x]]) return ans[x][id[y]];
return calc(fa[x], fa[y]) + a[x] * a[y];
}
int main() {
int n, q; 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", &fa[i]), P[dep[i] = dep[fa[i]] + 1].push_back(i);
ans[1][1] = a[1] * a[1], vis[0] = 1, id[1] = 1;
for (int i = 1; i <= n; i++) {
if (P[i].size() > B) continue;
int c = 0;
for (int x : P[i]) id[x] = ++c;
for (int x : P[i]) for (int y : P[i]) ans[x][id[y]] = calc(x, y);
vis[i] = 1;
}
while (q--) {
int x, y; scanf("%d%d", &x, &y);
printf("%lld\n", calc(x, y));
}
return 0;
}