#include constexpr int N = 500005; int n, m; int dep[N], size[N], wson[N], dfc, dfn[N], idfn[N]; std::vector tree[N]; void predfs(int u, int p) { dfn[u] = ++dfc; idfn[dfc] = u; size[u] = 1; dep[u] = dep[p] + 1; for (int v : tree[u]) { if (v == p) continue; predfs(v, u); size[u] += size[v]; if (size[v] > size[wson[u]]) wson[u] = v; } } int lpar[N], rpar[N], vis[N]; int findl(int x) { return lpar[x] == x ? x : lpar[x] = findl(lpar[x]); } int findr(int x) { return rpar[x] == x ? x : rpar[x] = findr(rpar[x]); } std::vector> e; void work(int u, int p, int o) { for (int v : tree[u]) { if (v == p) continue; if (v == wson[u]) continue; work(v, u, 0); } if (wson[u]) work(wson[u], u, 1); const auto ins = [&](int x) { vis[x] = 1; if (vis[x - 1]) { lpar[x] = x - 1; rpar[x - 1] = x; } if (vis[x + 1]) { lpar[x + 1] = x; rpar[x] = x + 1; } int l = findl(x), r = findr(x); e.push_back({r - l + 1, dep[u], l, r}); }; for (int v : tree[u]) { if (v == p) continue; if (v == wson[u]) continue; for (int i = dfn[v]; i < dfn[v] + size[v]; i++) ins(idfn[i]); } ins(u); if (!o) { for (int i = dfn[u]; i < dfn[u] + size[u]; i++) { int x = idfn[i]; vis[x] = 0; lpar[x] = rpar[x] = x; } } } struct BIT { int max[N]; void upd(int x, int v) { for (; x < N; x += x & -x) max[x] = std::max(max[x], v); } void clear(int x) { for (; x < N; x += x & -x) max[x] = 0; } int query(int x) { int res = 0; for (; x; x -= x & -x) res = std::max(res, max[x]); return res; } }; BIT bit; int ans[N]; void solve(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; solve(l, mid); solve(mid + 1, r); for (int i = mid + 1, j = l; i <= r; i++) { while (j <= mid && std::get<2>(e[j]) <= std::get<2>(e[i])) { auto [t, v, x, y] = e[j]; if (v > 0) bit.upd(n - y + 1, v); j++; } auto [t, v, x, y] = e[i]; if (v < 0) ans[-v] = std::max(ans[-v], bit.query(n - y + 1)); } for (int j = l; j <= mid; j++) { auto [t, v, x, y] = e[j]; if (v > 0) bit.clear(n - y + 1); } std::inplace_merge(e.begin() + l, e.begin() + mid + 1, e.begin() + r + 1, [](auto a, auto b) { return std::get<2>(a) < std::get<2>(b); }); } int main() { freopen("query.in", "r", stdin); freopen("query.out", "w", stdout); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n; for (int i = 1; i < n; i++) { int x, y; std::cin >> x >> y; tree[x].push_back(y); tree[y].push_back(x); } std::iota(lpar + 1, lpar + n + 1, 1); std::iota(rpar + 1, rpar + n + 1, 1); predfs(1, 0); work(1, 0, 1); std::cin >> m; for (int i = 1; i <= m; i++) { int l, r, k; std::cin >> l >> r >> k; e.push_back({k, -i, r - k + 1, l + k - 1}); } std::sort(e.begin(), e.end(), std::greater>()); solve(0, e.size() - 1); for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }