rt，一个理论最坏时间复杂度 $O(qn)$ 的代码可以直接通过，在洛谷上 $36$ 分。

思路是先预处理相邻两个点的 LCA，询问直接找到区间深度最小的位置然后往左右分治，来自洛谷的这个帖子

代码：

// superyijin AK IOI
// wangsiyuanZP AK IOI
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pair<int, int>>
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
#define pcnt __builtin_popcountll
using namespace std;
const int inf = (sizeof(int) == 4 ? 0x3f3f3f3f : 0x3f3f3f3f3f3f3f3f);
const int mod = 1e9 + 7;
const ld eps = 1e-7;
void chkmin(int &x, int y) { x = min(x, y); }
void chkmax(int &x, int y) { x = max(x, y); }
void inc(int &x, int y) { x = (x + y >= mod ? x + y - mod : x + y); }
void dec(int &x, int y) { x = (x - y < 0 ? x - y + mod : x - y); }
int ksm(int a, int b)
{
	int t = 1;
	while (b)
	{
		if (b & 1) t = t * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return t;
}
bool Mbe;
const int N = 2e5 + 10;
struct Bit
{
	int t[N];
	Bit() { memset(t, 0, sizeof(t)); }
	int lowbit(int x) { return x & -x; }
	void add(int x, int y) { while (x < N) t[x] += y, x += lowbit(x); }
	int sum(int x)
	{
		int ans = 0;
		while (x >= 1) ans += t[x], x -= lowbit(x);
		return ans;
	}
};
int fac[N], invfac[N];
void init(int n)
{
	fac[0] = 1;
	for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	invfac[n] = ksm(fac[n], mod - 2);
	for (int i = n - 1; i >= 0; i--) invfac[i] = invfac[i + 1] * (i + 1) % mod;
}
int A(int n, int m)
{
	if (m < 0 || m > n) return 0;
	return fac[n] * invfac[n - m] % mod;
}
int C(int n, int m)
{
	if (m < 0 || m > n) return 0;
	return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}
int tot, dep[500010], dfn[500010], id[1000010], w[500010], dp[20][1000010], f[20][500010], g[20][500010];
vector<int> v[500010];
void dfs(int x, int fa)
{
	dep[x] = dep[fa] + 1, id[dfn[x] = ++tot] = x;
	for (auto i : v[x])
	{
		if (i == fa) continue;
		dfs(i, x);
		id[++tot] = x;
	}
}
int lca(int x, int y)
{
	x = dfn[x], y = dfn[y];
	if (x > y) swap(x, y);
	int k = __lg(y - x + 1);
	return (dep[dp[k][x]] < dep[dp[k][y - (1 << k) + 1]] ? dp[k][x] : dp[k][y - (1 << k) + 1]);
}
int query(int l, int r)
{
	int x = __lg(r - l + 1);
	return max(f[x][l], f[x][r - (1 << x) + 1]);
}
int query_pos(int l, int r)
{
	int x = __lg(r - l + 1);
	return (w[g[x][l]] < w[g[x][r - (1 << x) + 1]] ? g[x][l] : g[x][r - (1 << x) + 1]);
}
int calc(int l, int r, int k)
{
	if (r - l + 1 < k) return 0;
	int p = query_pos(l, r);
	return max({w[p], calc(l, p - 1, k), calc(p + 1, r, k)});
}
void solve()
{
	int n, q;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(y), v[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= tot; i++) dp[0][i] = id[i];
	for (int j = 1; (1 << j) <= tot; j++) for (int i = 1; i <= tot - (1 << j) + 1; i++) dp[j][i] = (dep[dp[j - 1][i]] < dep[dp[j - 1][i + (1 << j - 1)]] ? dp[j - 1][i] : dp[j - 1][i + (1 << j - 1)]);
	for (int i = 1; i <= n; i++) f[0][i] = dep[i];
	for (int j = 1; (1 << j) <= n; j++) for (int i = 1; i <= n - (1 << j) + 1; i++) f[j][i] = max(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
	for (int i = 1; i < n; i++) w[i] = dep[lca(i, i + 1)], g[0][i] = i;
	for (int j = 1; (1 << j) < n; j++) for (int i = 1; i < n - (1 << j) + 1; i++) g[j][i] = (w[g[j - 1][i]] < w[g[j - 1][i + (1 << j - 1)]] ? g[j - 1][i] : g[j - 1][i + (1 << j - 1)]);
	cin >> q;
	while (q--)
	{
		int l, r, k;
		cin >> l >> r >> k;
		if (k == 1) cout << query(l, r) << '\n';
		else cout << calc(l, r - 1, k - 1) << '\n';
	}
}
bool Med;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << "MB" << endl;
	int t = 1;
	// cin >> t;
	while (t--) solve();
	return 0;
}
// superyijin AK IOI
// wangsiyuanZP AK IOI