题解

#include <bits/stdc++.h>
using namespace std;

constexpr int Spp = 1 << 20;
char buf[Spp], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, Spp, stdin), p1 == p2) ? EOF : *p1++)
template<typename T>
void read(T &x) {
    char c; int f = 1;
    do x = (c = getchar()) - '0';
    while (!isdigit(c) && c != '-');
    if (c == '-') x = 0, f = -1;
    while (isdigit(c = getchar()))
        x = x * 10 + (c - '0');
    x *= f;
}
template <typename T, typename ...Args>
void read(T &x, Args &...args) { read(x); read(args...); }

constexpr int N = 5e5 + 5;
constexpr int LG = 18;

vector<int> e[N];
int fz[N], fa[N], dep[N], lda, dfn[N];
int st[LG + 1][N];

void init(int u, int p) {
    fa[u] = p;
    dfn[u] = ++lda;
    fz[lda] = u;
    dep[u] = dep[p] + 1;
    for (int v : e[u])
        if (v != p)
            init(v, u);
}

int Max(int u, int v) {
    return dep[fz[u]] < dep[fz[v]] ? u : v;
}

int LCA(int u, int v) {
    if (u == v) return u;
    u = dfn[u]; v = dfn[v];
    if (u > v) swap(u, v);
    int z = __lg(v - u);
    return fa[fz[Max(st[z][v], st[z][u + (1 << z)])]];
}

vector<int> ans[N * 4], ans2[N * 4];
vector<pair<int, int>> lo[N * 4], ro[N * 4], oo[N * 4], lr[N * 4], nl[N * 4], nr[N * 4];
int LC[N * 4];

void build(int p, int L, int R) {
    ans[p].resize(R - L + 2);
    ans2[p].resize(R - L + 2);
    if (L == R) {
        ans[p][1] = dep[L];
        lo[p].emplace_back(L, L);
        ro[p].emplace_back(R, R);
        LC[p] = L;
        return;
    }
    int mid = (L + R) >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    LC[p] = LCA(LC[p << 1], LC[p << 1 | 1]);
    for (int i = 1; i <= mid - L + 1; ++i) ans[p][i] = ans[p << 1][i];
    for (int i = 1; i <= R - mid; ++i) ans[p][i] = max(ans[p][i], ans[p << 1 | 1][i]);
    lo[p] = lo[p << 1];
    ro[p] = ro[p << 1 | 1];
    for (auto [x, y] : lo[p << 1 | 1]) {
        nr[p].emplace_back(LCA(x, mid), y);
        lo[p].emplace_back(LCA(x, LC[p << 1]), y);
    }
    for (auto [x, y] : ro[p << 1]) {
        nl[p].emplace_back(LCA(x, mid + 1), y);
        ro[p].emplace_back(LCA(x, LC[p << 1 | 1]), y);
    }
    merge(nl[p].begin(), nl[p].end(), nr[p].begin(), nr[p].end(), back_inserter(oo[p]),
          [](auto x, auto y) { return dep[x.first] > dep[y.first]; });
    int l = mid, r = mid + 1, an = N;
    for (auto [x, y] : oo[p]) {
        l = min(l, y);
        r = max(r, y);
        lr[p].emplace_back(l, r);
        an = min(an, dep[x]);
        ans2[p][r - l + 1] = max(ans2[p][r - l + 1], an);
    }
    ans[p][R - L + 1] = max(ans[p][R - L + 1], ans2[p][R - L + 1]);
    for (int i = R - L; i >= 1; --i)
        ans[p][i] = max({ans[p][i], ans2[p][i], ans[p][i + 1]});
    lo[p << 1].clear(); lo[p << 1].shrink_to_fit();
    ro[p << 1 | 1].clear(); ro[p << 1 | 1].shrink_to_fit();
}

int n;

int qry(int p, int l, int r, int k, int L, int R) {
    if (l <= L && R <= r)
        return k > (R - L + 1) ? 0 : ans[p][k];
    int mid = (L + R) >> 1;
    int res = 0;
    if (l <= mid) res = max(res, qry(p << 1, l, r, k, L, mid));
    if (r > mid) res = max(res, qry(p << 1 | 1, l, r, k, mid + 1, R));
    if (k <= R - L + 1 && l <= mid && r > mid) {
        if (l <= L) {
            if (r - k + 1 >= L)
                res = max(res, min(ans2[p][k], dep[nl[p][max(0, mid - (r - k + 1))].first]));
        } else if (r >= R) {
            if (l + k - 1 <= R)
                res = max(res, min(ans2[p][k], dep[nr[p][max(0, (l + k - 1) - mid - 1)].first]));
        } else {
            int ll = 0, rr = R - L;
            int l1 = l, l2 = r - k + 1;
            int r2 = r, r1 = l + k - 1;
            while (ll <= rr) {
                int md = (ll + rr) >> 1;
                auto [LL, RR] = lr[p][md];
                if (RR - LL + 1 < k) {
                    ll = md + 1;
                    continue;
                }
                if (LL <= l1 && RR >= r1 || LL <= l2 && RR >= r2 || LL >= l && LL + k - 1 <= r || RR <= r && RR - k + 1 >= l) {
                    res = max(res, dep[oo[p][md].first]);
                    rr = md - 1;
                } else ll = md + 1;
            }
        }
    }
    return res;
}

int main() {
    read(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        read(u, v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    init(1, 0);
    iota(st[0] + 1, st[0] + 1 + n, 1);
    for (int i = 1; i <= LG; ++i)
        for (int j = 1 << i; j <= n; ++j)
            st[i][j] = Max(st[i - 1][j], st[i - 1][j - (1 << (i - 1))]);
    build(1, 1, n);
    int q;
    read(q);
    while (q--) {
        int l, r, k;
        read(l, r, k);
        cout << qry(1, l, r, k, 1, n) << "\n";
    }
    return 0;
}