出题学长的祖传好题。

学长的做法是：考虑 BFS 序，先预处理出每个点 $x$ 到其第 $2^k$ 级祖先路上的最大值。然后考虑处理每个询问，我们先找出对应的子树，然后在这个 BFS 序列上进行二分，找到对应点（感觉说的很抽象，大家结合代码理解）复杂度大概是 $\mathcal{O}(n\log^2 n)$ 的

我的做法是：考虑每个点维护一颗以深度为下标的线段树，然后实际上这个过程就是把每个点上的线段树合并，所以总时间复杂度实际上是可以做到 $\mathcal{O}(n\log n)$。当然你也可以用 DSU on tree 来实现，反正就是多一个 log 的事。

学长的 std:

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 500005;

struct edge {
	int v, pre;
} e[MAXN<<1];
int N, T, C[MAXN], fst[MAXN];
// C: the maximum in the node's tree
int qwq[MAXN], pq[MAXN], pd[MAXN], pl[MAXN], pr[MAXN];
// qwq: bfs
// pq: nodes' poi in qwq
// pd: nodes' deep in qwq
// pl: the left poi of the same deep in qwq
int maxn[MAXN][25];
int vis[MAXN], dep[MAXN], depp[MAXN];
int fth[MAXN][25], son[MAXN][25], lg[MAXN];

inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }
inline int read()
{
	register int o = 0;
	register char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >='0' && c <='9') o = (o<<3)+(o<<1)+(c&15), c = getchar();
	return o;
}
inline void adde(int a, int b, int k)
{
	e[k] = (edge){b, fst[a]}, fst[a] = k;
}
void bfs()
{
	register int h = 0, t = 1, uu, vv;
	qwq[1] = 1, vis[1] = 1, pd[1] = 0;
	do {
		uu = qwq[++h], pq[uu] = h;
		for (register int o=fst[uu]; o; o=e[o].pre) if (!vis[e[o].v]) {
			vv = e[o].v, qwq[++t] = vv, vis[vv] = 1, pd[t] = pd[h] + 1;
		}
	} while (h < t);
	for (register int i=1; i<=N; i++) pr[pd[i]] = i;
	for (register int i=N; i>=1; i--) pl[pd[i]] = i;
}
void dfs(int k, int d)
{
	vis[k] = 0, dep[k] = d;
	for (register int i=1; i<=lg[d]; i++)
		fth[k][i] = fth[fth[k][i-1]][i-1];
	for (register int o=fst[k]; o; o=e[o].pre) if (vis[e[o].v]) {
		fth[e[o].v][0] = k, dfs(e[o].v, d+1);
		C[k] = max(C[k], C[e[o].v]);
		if (depp[k] < depp[e[o].v] + 1) {
			depp[k] = depp[e[o].v] + 1;
			son[k][0] = e[o].v;
		}
	}
	for (register int i=1; i<=lg[depp[k]]; i++)
		son[k][i] = son[son[k][i-1]][i-1];
}
void init()
{
	N = read();
	for (int i=1; i<=N; i++) C[i] = read();
	for (int i=1; i< N; i++) {
		int a = read(), b = read();
		adde(a, b, i), adde(b, a, i+N);
	}
	for (int i=1; i<=N; i++)
		lg[i] = lg[i-1] + ((1<<(lg[i-1]+1)) == i);
	bfs(), dfs(1, 0);
	for (register int i=1; i<=N; i++) maxn[i][0] = C[qwq[i]];
	for (register int k=1; k<=lg[N]; k++)
		for (register int i=1; i+(1<<k)-1<=N; i++)
			maxn[i][k] = max(maxn[i][k-1], maxn[i+(1<<(k-1))][k-1]);
}
int lca(int a, int b)
{
    if (dep[a] < dep[b]) a ^= b ^= a ^= b;
    while (dep[a] > dep[b]) a = fth[a][lg[dep[a]-dep[b]]];
    if (a == b) return a;
    for (register int i=lg[dep[a]]; i>=0; i--)
        if (fth[a][i] != fth[b][i]) a = fth[a][i], b = fth[b][i];
    return fth[a][0];
}
void work()
{
	T = read();
	for (; T; T--) {
		register int uu = read(), vv = uu, dd = read(), pv;
		while (dep[vv] < dep[uu] + dd) vv = son[vv][lg[dep[uu]-dep[vv]+dd]];
		pv = pq[vv];
		register int l = pl[pd[pv]] - 1, r = pr[pd[pv]] + 1, tmp, mid;
		tmp = pv; //(l, tmp]
		while (l + 1 < tmp) {
			mid = (l + tmp) >> 1;
			if (dep[lca(vv, qwq[mid])] < dep[uu]) l = mid; else tmp = mid;
		}
		tmp = pv; //[tmp, r)
		while (tmp + 1 < r) {
			mid = (tmp + r) >> 1;
			if (dep[lca(vv, qwq[mid])] < dep[uu]) r = mid; else tmp = mid;
		}
		l++, r--;
		int ans = max(maxn[l][lg[r-l+1]], maxn[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
		printf("%d\n", ans);
	}
}
int main()
{
	init();
	work();
}