rt，单 log，但是人傻常数大

代码：

#include <bits/stdc++.h>
#define For(i, a, b) for (register int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (register int i = (a); i >= (b); i --)
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<19,stdin),S==T)?EOF:*S++)
char B[1<<15],*S=B,*T=B;
using namespace std;
int n, q, k, k_, cnt, ccnt;
int fa[500005][19], ans[500005], dep[500005], pre[20], head[500005], Head[500005];
int ls[10000005], rs[10000005], root[500005], lmax[10000005], rmax[10000005];
int mx[2000005], st[19][500005], lg[500005];
struct Edge {int v, nxt;}e[1000005];
struct node {int v, nxt;}nn[500005];
inline void add (int u, int v) {
	e[++ k] = {v, head[u]};
	head[u] = k;
}
inline void Add (int u, int v) {
	nn[++ k_] = {v, Head[u]};
	Head[u] = k_;
}
struct Node {int L, R, len, res;}a[1000005];
inline bool cmp1 (Node n1, Node n2) {return n1.L < n2.L;};
inline bool cmp2 (Node n1, Node n2) {return n1.len > n2.len;}
struct Query {int l, r, k, id;}u[500005];
inline bool cmpq1 (Query q1, Query q2) {return q1.l < q2.l;}
inline bool cmpq2 (Query q1, Query q2) {return q1.k > q2.k;}
inline int read () {
	char ch = getchar ();
	int x = 0;
	while (ch < '0' || ch > '9') ch = getchar ();
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar ();
	}
	return x;
}
inline void dfs1 (int u) {
	For (i, 1, 18) fa[u][i] = fa[fa[u][i - 1] ][i - 1];
	st[0][u] = dep[u];
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa[u][0]) continue;
		fa[v][0] = u;
		dep[v] = dep[u] + 1;
		dfs1 (v);
	}
}
inline int lca (int u, int v) {
	if (dep[u] < dep[v]) swap (u, v);
	foR (i, 18, 0) if (dep[fa[u][i] ] >= dep[v]) u = fa[u][i];
	if (u == v) return u;
	foR (i, 18, 0) if (fa[u][i] != fa[v][i]) {
		u = fa[u][i];
		v = fa[v][i];
	}
	return fa[u][0];
}
inline void pushup (int l, int r, int k) {
	int mid = l + r >> 1;
	if (rmax[rs[k] ] == r - mid) rmax[k] = r - mid + rmax[ls[k] ];
	else rmax[k] = rmax[rs[k] ];
	if (lmax[ls[k] ] == mid - l + 1) lmax[k] = lmax[ls[k] ] + lmax[rs[k] ];
	else lmax[k] = lmax[ls[k] ];
}
inline int merge (int l, int r, int k1, int k2) {
	if (!k1 || !k2) return k1 | k2;
	if (l == r) {
		lmax[k2] = max (lmax[k1], lmax[k2]);
		rmax[k2] = max (rmax[k1], rmax[k2]);
		return k2;
	}
	int mid = l + r >> 1;
	ls[k2] = merge (l, mid, ls[k1], ls[k2]);
	rs[k2] = merge (mid + 1, r, rs[k1], rs[k2]);
	pushup (l, r, k2);
	return k2;
}
inline int query (int l, int r, int k, int x, int y, int type) {
	if (!k) return 0;
	if (x <= l && y >= r) return (type == 1 ? lmax[k] : rmax[k]);
	int mid = l + r >> 1;
	if (y <= mid) return query (l, mid, ls[k], x, y, type);
	if (x > mid) return query (mid + 1, r, rs[k], x, y, type);
	if (type == 1) {
		int xx = query (l, mid, ls[k], x, y, type);
		if (xx == mid - x + 1) return xx + query (mid + 1, r, rs[k], x, y, type);
		return xx;
	}
	int xx = query (mid + 1, r, rs[k], x, y, type);
	if (xx == y - mid) return xx + query (l, mid, ls[k], x, y, type);
	return xx;
}
inline void update (int l, int r, int &k, int x) {
	if (!k) k = ++ cnt;
	if (l == r) return void (lmax[k] = rmax[k] = 1);
	int mid = l + r >> 1;
	if (x <= mid) update (l, mid, ls[k], x);
	else update (mid + 1, r, rs[k], x);
	pushup (l, r, k);
}
inline void dfs2 (int u) {
	update (1, n, root[u], u);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa[u][0]) continue;
		dfs2 (v);
		root[u] = merge (1, n, root[v], root[u]);
	}
	for (int j = Head[u]; j; j = nn[j].nxt) {
		int i = nn[j].v;
		a[++ ccnt] = {i - query (1, n, root[u], 1, i, 2) + 1, i + query (1, n, root[u], i + 1, n, 1), 0, dep[u]};
		a[ccnt].len = a[ccnt].R - a[ccnt].L + 1;
	}
}
inline void modify (int l, int r, int k, int x, int y) {
	if (l == r) return void (mx[k] = max (mx[k], y) );
	int mid = l + r >> 1;
	if (x <= mid) modify (l, mid, k << 1, x, y);
	else modify (mid + 1, r, k << 1 | 1, x, y);
	mx[k] = max (mx[k << 1], mx[k << 1 | 1]);
}
inline int qmax (int l, int r, int k, int x, int y) {
	if (x > y) return 0;
	if (x <= l && y >= r) return mx[k];
	int mid = l + r >> 1, res = 0;
	if (x <= mid) res = qmax (l, mid, k << 1, x, y);
	if (y > mid) res = max (res, qmax (mid + 1, r, k << 1 | 1, x, y) );
	return res;
}
inline void func1 () {
	sort (a + 1, a + ccnt + 1, cmp1);
	sort (u + 1, u + q + 1, cmpq1);
	int tail = 0;
	For (i, 1, q) {
		if (u[i].k == 1) continue;
		while (tail != ccnt && a[tail + 1].L <= u[i].l) modify (1, n, 1, a[tail + 1].R, a[tail + 1].res), ++ tail;
		ans[u[i].id] = max (ans[u[i].id], qmax (1, n, 1, u[i].r, n) );
	}
}
inline void func2 () {
	sort (a + 1, a + ccnt + 1, cmp2);
	sort (u + 1, u + q + 1, cmpq2);
	For (i, 1, 2000000) mx[i] = 0;
	int tail = 0;
	For (i, 1, q) {
		if (u[i].k == 1) continue;
		while (tail != ccnt && a[tail + 1].R - a[tail + 1].L + 1 >= u[i].k) modify (1, n, 1, a[tail + 1].R, a[tail + 1].res), ++ tail;
		ans[u[i].id] = max (ans[u[i].id], qmax (1, n, 1, u[i].l + u[i].k - 1, u[i].r - 1) );
	}
	For (i, 1, 2000000) mx[i] = 0;
	tail = 0;
	For (i, 1, q) {
		if (u[i].k == 1) continue;
		while (tail != ccnt && a[tail + 1].R - a[tail + 1].L + 1 >= u[i].k) modify (1, n, 1, a[tail + 1].L, a[tail + 1].res), ++ tail;
		ans[u[i].id] = max (ans[u[i].id], qmax (1, n, 1, u[i].l + 1, u[i].r - u[i].k + 1) );
	}
}
inline void write (int x) {
	if (x < 10) {
		putchar (x + 48);
		return;
	}
	write (x / 10);
	putchar (x % 10 + 48);
}
signed main () {
	lg[1] = 0;
	For (i, 2, 500000) lg[i] = lg[i / 2] + 1;
	For (i, 0, 20) pre[i] = 1 << i;
	n = read ();
	For (i, 1, n) root[i] = i;
	cnt = n;
	For (i, 2, n) {
		int u = read (), v = read ();
		add (u, v);
		add (v, u);
	}
	dep[1] = 1;
	dfs1 (1);
	For (i, 1, n - 1) Add (lca (i, i + 1), i);
	dfs2 (1);
	q = read ();
	For (j, 1, 18) For (i, 1, n - pre[j] + 1) st[j][i] = max (st[j - 1][i], st[j - 1][i + pre[j - 1] ]);
	For (i, 1, q) {
		u[i] = {read (), read (), read (), i};
		if (u[i].k == 1) {
			int l = lg[u[i].r - u[i].l + 1];
			ans[u[i].id] = max (st[l][u[i].l], st[l][u[i].r - pre[l] + 1]);
		}
	}
	func1 ();
	func2 ();
	For (i, 1, q) {
	    write (ans[i]);
	    putchar ('\n');
	}
	return 0;
}