题意：给出一棵 $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
*/