题意：给出一棵 \(n\) 个点的树，每个点有点权 \(a_i\)，再给出 \(m\) 条路径 \((s_i,t_i)\)。\(q\) 次询问一个 \(x\)，问在一条路径上选两个点 \(u<v\) 满足 \(a_u+a_v = x\) 的个数。
\(a_i\le n\le 10^5,m\le 2\times 10^5, q\le 2000\)。
做法：
我们假设路径 \(T\) 可以弄出来一个多项式 \(F(T) = \sum \limits_{u\in path(T)}x^{a_u}\)，那么我们就等于要求 \(\sum \frac{F^2(T)-F(T^2)}{2}\) 的一项的系数。难点在于怎么求 \(F^2(T)\)，接下来只考虑这个东西。
直接对路径考虑很麻烦，我们考虑把路径拆成若干条 \(1\to u\) 的路径，那么 \(F(T) = G(s)+G(t)-G(d)-G(f_d)\)，这里 \(G(u)\) 是 \(1\to u\) 路径上点权所构成的生成函数，\(d\) 是 lca，\(f_u\) 是 \(u\) 的父亲。把平方拆开，那么最后要求的东西直接拆开就可以变成若干个 \(coef \times G(x)\times G(y)\) 的形式。
但是直接考虑路径有点麻烦，我们考虑排到序列上，用欧拉序来描述这个东西，进入 \(u\) 子树的时候加上一个 \(x^{a_u}\)，出子树的时候减去一个 \(x^{a_u}\) 即可。那么现在就变成了，我有一个序列 \(a\) 和权值序列 \(v\)，我一条路径对询问为 \(k\) 的贡献为若干个 \(\sum\limits_{i\le x}\sum\limits_{j\le y,a_i+a_j=k}v_iv_j\) 这样一个东西，如何快速求解。
有加法等于一个东西，这个东西大概率做不到 polylog，我们考虑对其分块，我们对 \(i\) 这一维分块。对于整块，我们把贡献挂在 \(j\) 这边，可以直接维护 \(j\) 这边的差分然后再前缀和起来，算出来每个数的出现次数，然后枚举每个块中元素对每个询问的贡献即可，复杂度 \(O(\frac{n^2}{B}+qn)\)。
然后再考虑散块，我们可以扫 \(j\) 这边，暴力遍历散块，计算对 \(j\) 这边的贡献即可，复杂度 \(O(nB+qn)\)。
取 \(B=\sqrt n\) 即可做到 \(O(\sqrt n(n+q))\)，实际因为要一个路径拆成 \(10\) 组贡献，把块长开小会更优。结合代码会更好理解。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5, B = 200;
int n, a[maxn], m, q, x[maxn], s[maxn], t[maxn];
vector<int> e[maxn];
struct node {int x, val;
} st[maxn];
int tot, dfn[maxn], f[maxn][21], dep[maxn];
void dfs(int u, int fa) {f[u][0] = fa; dep[u] = dep[fa] + 1;st[++tot] = {u, 1}; dfn[u] = tot;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dfs(v, u);}st[++tot] = {u, -1};
}
int lca(int x, int y) {if(dep[x] < dep[y])swap(x, y);for (int i = 20; i >= 0; i--)if(dep[f[x][i]] >= dep[y])x = f[x][i];for (int i = 20; i >= 0; i--)if(f[x][i] != f[y][i])x = f[x][i], y = f[y][i];return (x == y ? x : f[x][0]);
}
int xt[maxn * 10], yt[maxn * 10], val[maxn * 10], tot1;
void prepare() {for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)f[i][j] = f[f[i][j - 1]][j - 1];
}
int l[maxn], r[maxn], pos[maxn];
void init() {for (int i = 1; i <= tot; i++) {pos[i] = (i - 1) / B + 1;if(!l[pos[i]])l[pos[i]] = i;r[pos[i]] = i;}
}
vector<int> vec[maxn], add[maxn], ers[maxn];
int cf[maxn], ans[maxn], cnt[maxn], s1[maxn];
void redfs(int u, int fa) {for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;redfs(v, u);cf[u] += cf[v];}for (int i = 1; i <= q; i++)if(2 * a[u] == x[i])ans[i] -= cf[u];
}
signed main() {
// freopen("test.in", "r", stdin);
// freopen("std.out", "w", stdout);ios::sync_with_stdio(false);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i < n; i++) {int x, y; cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}dfs(1, 0);prepare();cin >> m;for (int i = 1; i <= m; i++) {cin >> s[i] >> t[i];int d = lca(s[i], t[i]);xt[++tot1] = s[i], yt[tot1] = t[i], val[tot1] = 2;xt[++tot1] = s[i], yt[tot1] = s[i], val[tot1] = 1;xt[++tot1] = t[i], yt[tot1] = t[i], val[tot1] = 1;xt[++tot1] = d, yt[tot1] = d, val[tot1] = 1;xt[++tot1] = s[i], yt[tot1] = d, val[tot1] = -2;xt[++tot1] = t[i], yt[tot1] = d, val[tot1] = -2;if(f[d][0])xt[++tot1] = s[i], yt[tot1] = f[d][0], val[tot1] = -2,xt[++tot1] = t[i], yt[tot1] = f[d][0], val[tot1] = -2,xt[++tot1] = d, yt[tot1] = f[d][0], val[tot1] = 2,xt[++tot1] = f[d][0], yt[tot1] = f[d][0], val[tot1] = 1;//cout << s[i] << " " << t[i] << " " << d << endl;}for (int i = 1; i <= tot1; i++)xt[i] = dfn[xt[i]], yt[i] = dfn[yt[i]];
// cout << tot1 << endl;cin >> q;for (int i = 1; i <= q; i++)cin >> x[i];init();for (int i = 1; i <= tot1; i++)vec[pos[xt[i]] - 1].push_back(i);for (int i = pos[tot]; i >= 1; i--) {for (int j = 0; j < vec[i].size(); j++)cf[yt[vec[i][j]]] += val[vec[i][j]];for (int i = 1; i <= n; i++)cnt[a[i]] = 0;for (int i = tot; i >= 1; i--)cf[i] = cf[i + 1] + cf[i], cnt[a[st[i].x]] += cf[i] * st[i].val;for (int j = l[i]; j <= r[i]; j++) {for (int k = 1; k <= q; k++)if(x[k] > a[st[j].x])ans[k] += st[j].val * cnt[x[k] - a[st[j].x]];}for (int i = 1; i <= tot; i++)cf[i] = cf[i] - cf[i + 1];}
// for (int i = 1; i <= q; i++)
// cout << ans[i] << endl;for (int i = 1; i <= tot1; i++)add[yt[i]].push_back(i);for (int i = 1; i <= n; i++)cnt[a[i]] = 0;for (int i = tot; i >= 1; i--) {for (int j = 0; j < add[i].size(); j++) {int id = add[i][j];for (int k = l[pos[xt[id]]]; k <= xt[id]; k++)cnt[a[st[k].x]] += st[k].val * val[id];}for (int j = 1; j <= q; j++)if(x[j] >= a[st[i].x]) {ans[j] += cnt[x[j] - a[st[i].x]] * st[i].val;
// if(cnt[x[j] - a[st[i].x]])
// cout << i << " " << j << " " << st[i].x << " debug" << st[i].val << " " << ans[j] << endl;}}
// cout << ans[2] << endl;for (int i = 0; i <= n; i++)cf[i] = 0;for (int i = 1; i <= m; i++)cf[s[i]]++, cf[t[i]]++,cf[lca(s[i], t[i])]--, cf[f[lca(s[i], t[i])][0]]--;
// cout << ans[6] << endl;redfs(1, 0);for (int i = 1; i <= q; i++)cout << ans[i] / 2 << endl;return 0;
}
/*
8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
1
3 8
1
2
*/