我这么写其他情况下都可以正常运行，但是链的大样例跑起来就死循环，求大佬指正（链的函数是solve3）

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q, l[N], r[N], k[N];
int fa[N][20], dep[N];
int pre[5005][5005], st[N][20], a[N], kth;
vector<int> g[N];
void dfs(int u, int f) {
	dep[u] = dep[f] + 1;
	fa[u][0] = f;
	for(int i = 1;i <= __lg(dep[u]);++i)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	for(auto v : g[u]) {
		if(v == f) continue;
		dfs(v, u);
	}
}
int lca(int a, int b) {
	if(dep[a] < dep[b]) swap(a, b);
	for(int i = 19;i >= 0;--i)
		if(dep[fa[a][i]]>=dep[b]) a = fa[a][i];
	if(a == b) return a;
	for(int i = 19;i >= 0;--i)
		if(fa[a][i]!=fa[b][i]) a = fa[a][i], b = fa[b][i];
	return fa[a][0];
}
void solve1() {
	for(int i = 1;i <= n;++i) pre[i][i] = i;
	for(int i = 1;i <= n;++i)
		for(int j = i+1;j <= n;++j)
			pre[i][j] = lca(pre[i][j-1], j);
	for(int i = 1;i <= q;++i) {
		int mx = 0;
		for(int j = l[i];j+k[i]-1 <= r[i];++j)
			mx = max(mx, dep[pre[j][j+k[i]-1]]);
		printf("%d\n", mx);
	}
}
void solve2() {
	memset(st, 0x3f, sizeof st);
	for(int i = 1;i <= n;++i) st[i][0] = i;
	for(int j = 1;j <= __lg(n);++j)
		for(int i = 1;i+(1<<j)-1 <= n;++i)
			st[i][j] = lca(st[i][j-1], st[i+(1<<j-1)][j-1]);
	for(int i = 1;i <= q;++i) {
		int cov = __lg(r[i]-l[i]+1);
		int mn = lca(st[l[i]][cov], st[r[i]-(1<<cov)+1][cov]);
		printf("%d\n", dep[mn]);
	}
}
void solve3() {
	int p = 1, cnt = 2;
	a[1] = 1;
	p = g[1][0];
	while(g[p].size() != 1) {
		a[cnt] = p;
		p = g[p][1];
		++cnt;
	}
	a[cnt] = p;
	for(int i = 1;i <= cnt;++i) st[i][0] = dep[i];
	for(int j = 1;j <= __lg(n);++j)
		for(int i = 1;i+(1<<j)-1 <= n;++i)
			st[i][j] = min(st[i][j-1], st[i+(1<<j-1)][j-1]);
	for(int i = 1;i <= q;++i) {
		int cov = __lg(r[i]-l[i]+1);
		int mn = min(st[l[i]][cov], st[r[i]-(1<<cov)+1][cov]);
		printf("%d\n", mn);
	}
}
int main () {
	scanf("%d", &n);
	for(int i = 1, u, v;i < n;++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	dfs(1, 0);
	scanf("%d", &q);
	int al = 0;
	for(int i = 1;i <= q;++i) {
		scanf("%d%d%d", l+i, r+i, k+i);
		if(k[i] == r[i]-l[i]+1) ++al; 
	}
	if(n <= 5000) solve1();
	else if(al == q) solve2();
	else solve3();
    return 0;
}