rt，目前战况。

能过除了 $5 \times 10^5$ 的链之外的所有数据，然后这些数据全部卡满 2.20s，问如何才能卡过，悬两关。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long int ll;
using pii = pair<int, int>;
constexpr int maxn = 5e5 + 10, mod = 998244353, inf = 1e6; int K, FG, NOW;
int rt[maxn], n, h[maxn], cnt = 0, tot = 0, d[maxn], a[maxn], Q; vector<int> g[maxn];
struct edge { int to, nxt; } nd[maxn << 1];
inline void add(int u, int v) { nd[cnt].nxt = h[u], nd[cnt].to = v, h[u] = cnt++; }
struct Node { int l, r; ll mx, sum, lsm, rsm; Node() { l = r = 0, lsm = rsm = sum = mx = -inf; } } t[maxn * 21];
#define ls(x) (t[x].l)
#define rs(x) (t[x].r)
#define mx(x) (t[x].mx)
#define sum(x) (t[x].sum)
#define lsm(x) (t[x].lsm)
#define rsm(x) (t[x].rsm)
#define mid (l + r >> 1)
inline void up(int x) {
	sum(x) = sum(ls(x)) + sum(rs(x));
	lsm(x) = max(lsm(ls(x)), sum(ls(x)) + lsm(rs(x)));
	rsm(x) = max(rsm(rs(x)), sum(rs(x)) + rsm(ls(x)));
	mx(x) = max({ mx(ls(x)), mx(rs(x)), rsm(ls(x)) + lsm(rs(x)) });
}
void mdf(int l, int r, int k, int p, int& x) {
	t[x = ++tot] = t[p];
	if (l == r) return sum(x) = lsm(x) = rsm(x) = mx(x) = 1, void();
	k <= mid ? mdf(l, mid, k, ls(p), ls(x)) : mdf(mid + 1, r, k, rs(p), rs(x)); up(x);
}
Node qry(int l, int r, int ql, int qr, int x) {
	//++K;
	if (!x || ql <= l && r <= qr || FG) return t[x];
	if (qr <= mid) return qry(l, mid, ql, qr, ls(x));
	else if (ql > mid) return qry(mid + 1, r, ql, qr, rs(x));
	else {
		const Node& u = qry(l, mid, ql, qr, ls(x)), & v = qry(mid + 1, r, ql, qr, rs(x)); Node w; if (FG) return w;
		w.sum = u.sum + v.sum, w.lsm = max(u.lsm, u.sum + v.lsm), w.rsm = max(v.rsm, v.sum + u.rsm), w.mx = max({ u.mx, v.mx, u.rsm + v.lsm });
		if (w.mx >= NOW) FG = 1;
		return w;
	}
}
int s[20][maxn], b[20][maxn], dfn[maxn], dct = 0;
void dfs(int u, int f) {
	s[0][dfn[u] = ++dct] = f; d[u] = d[f] + 1;
	for (int i = h[u]; ~i; i = nd[i].nxt) {
		int v = nd[i].to;
		if (v != f) dfs(v, u);
	}
}
int st[20][maxn], lg[maxn];
inline int ck(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline int rmq(int l, int r) {
	int g = lg[r - l + 1];
	return max(st[g][l], st[g][r - (1 << g) + 1]);
}
inline int rmqB(int l, int r) {
	int g = lg[r - l + 1];
	return min(b[g][l], b[g][r - (1 << g) + 1]);
}
inline int lca(int u, int v) {
	if (u == v) return u;
	else if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
	int g = lg[v - u++];
	return ck(s[g][u], s[g][v - (1 << g) + 1]);
}
inline int read() {
	int x = 0; char c = 0;
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}
int main() {
	//freopen("D:\\query4.in", "r", stdin);
	//freopen("D:\\query.out", "w", stdout);
	memset(h, -1, sizeof(h));
	n = read();
	for (int i = 2, u, v; i <= n; i++) {
		lg[i] = lg[i >> 1] + 1;
		u = read(), v = read(), add(u, v), add(v, u);
	}
	dfs(1, 0);
	rep(i, 1, n) st[0][i] = d[i]; int MX = 0; 
	rep(i, 1, 19) rep(j, 1, n - (1 << i - 1)) {
		st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
		s[i][j] = ck(s[i - 1][j], s[i - 1][j + (1 << i - 1)]);
	}
	rep(i, 1, n - 1) g[b[0][i] = d[lca(i, i + 1)]].pb(i); 
	rep(i, 1, 19) rep(j, 1, n - 1 - (1 << i - 1)) b[i][j] = min(b[i - 1][j], b[i - 1][j + (1 << i - 1)]);
	per(o, n, 1) {
		rt[o] = rt[o + 1];
		for (int x : g[o]) MX = max(MX, o), mdf(1, n, x, rt[o], rt[o]);
	}
	Q = read();
	while (Q--) {
		int l, r, k;
		l = read(), r = read(), k = read(); NOW = k;
		if (k == 1) printf("%d\n", rmq(l, r));
		else if (k == r - l + 1) printf("%d\n", rmqB(l, r - 1));
		else {
			--r, --k; //< w 的都不能选的前提下，[l, r - 1] 中是否存在 >= k - 1 的子段
			int L = 1, R = MX, M, ans = 0;
			while (L <= R) {
				M = L + R >> 1; 
				if (mx(rt[M]) >= k && qry(1, n, l, r, rt[M]).mx >= k || FG) L = M + 1, ans = M;//只能选 >= M 的
				else R = M - 1; FG = 0;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}