思路与算法

先求相邻编号点的LCA深度 $b_i=dep(LCA(i,i+1))$。连续区间至少两点时，它的LCA深度就是对应 $b$ 区间的最小值。扩大区间不能让LCA更深，所以“长度至少 $k$”等价于检查恰好长度 $k$。$k=1$ 直接查询最大单点深度。

令 $h=k-1$。每个 $b_i$ 的最小笛卡尔树子树给出一个最大无更小值区间 $[A,B]$，区间内都至少为 $b_i$。它能在询问的 $b$ 范围 $[l,r-1]$ 中容纳长度 $h$，当且仅当 $B-A+1\ge h$、$A\le r-h$、$B\ge l+h-1$。按 $h$ 从大到小离线处理，激活跨度足够的点 $(A,B,b_i)$，外层Fenwick维护 $A$ 前缀，内层离散Fenwick维护 $B$ 后缀的最大 $b_i$，返回二维偏序最大值。

正确性说明

连续点集合的最深公共祖先等于所有相邻对LCA的公共祖先，其中最浅的相邻LCA已经是全集的公共祖先，故其深度为相邻LCA深度的最小值。每个长度 $h$ 的窗口，其最小值在某个笛卡尔树结点取得，并被该结点子树跨度包含；反之，跨度与询问交集只要至少为 $h$ 就能选出一个完整窗口，其最小值至少为该结点值。交集长度条件恰等价于算法的三个不等式。因此所有激活点的二维查询最大值给出最优窗口最小值，也就是题目答案。

复杂度

树、倍增祖先、相邻LCA和静态深度最大值初始化 $O(n\log n)$。Cartesian边界为 $O(n)$，二维离散坐标初始化 $O(n\log^2n)$ 上界，存储 $O(n\log n)$。排序、激活与询问总时间 $O((n+q)\log^2n)$，总空间 $O(n\log n+q)$。相邻LCA数组单调时直接按窗口端点取得答案，免去二维结构。

易错点

$k=1$ 不使用长度0的 $b$ 窗口；n=1时没有相邻LCA数组。相同最小值的笛卡尔边界要一侧严格、一侧不严格，保证存在覆盖整段的候选。树编号顺序不是DFS顺序。原题内存1024MiB保持不改，若本机原生容量配置拒绝，准备通过不等于已验收入库。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Point {
    int l, r, len, value;
};
struct Query {
    int l, r, h, id;
};
struct Fenwick2D {
    int n;
    vector<vector<int>> ys, tree;
    Fenwick2D(int n, const vector<Point> &p) : n(n), ys(n + 1), tree(n + 1) {
        for (auto &v : p)
            for (int x = v.l; x <= n; x += x & -x)
                ys[x].push_back(v.r);
        for (int x = 1; x <= n; x++) {
            auto &v = ys[x];
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            tree[x].assign(v.size() + 1, 0);
        }
    }
    void update(int x, int y, int v) {
        for (; x <= n; x += x & -x) {
            int z = ys[x].end() - lower_bound(ys[x].begin(), ys[x].end(), y);
            for (; z < (int)tree[x].size(); z += z & -z)
                tree[x][z] = max(tree[x][z], v);
        }
    }
    int query(int x, int y) {
        int ans = 0;
        for (; x; x -= x & -x) {
            int z = ys[x].end() - lower_bound(ys[x].begin(), ys[x].end(), y);
            for (; z; z -= z & -z)
                ans = max(ans, tree[x][z]);
        }
        return ans;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int LOG = 1;
    while ((1 << LOG) <= n)
        ++LOG;
    vector<vector<int>> up(LOG, vector<int>(n + 1));
    vector<int> depth(n + 1), order(1, 1);
    depth[1] = 1;
    for (size_t j = 0; j < order.size(); j++) {
        int u = order[j];
        for (int v : g[u])
            if (v != up[0][u]) {
                up[0][v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
    }
    for (int z = 1; z < LOG; z++)
        for (int u = 1; u <= n; u++)
            up[z][u] = up[z - 1][up[z - 1][u]];
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v])
            swap(u, v);
        int d = depth[u] - depth[v];
        for (int z = 0; z < LOG; z++)
            if (d >> z & 1)
                u = up[z][u];
        if (u == v)
            return u;
        for (int z = LOG - 1; z >= 0; z--)
            if (up[z][u] != up[z][v]) {
                u = up[z][u];
                v = up[z][v];
            }
        return up[0][u];
    };
    int base = 1;
    while (base < n)
        base *= 2;
    vector<int> mx(2 * base);
    for (int i = 1; i <= n; i++)
        mx[base + i - 1] = depth[i];
    for (int i = base - 1; i; i--)
        mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
    auto maxdepth = [&](int l, int r) {
        int ans = 0;
        for (l += base - 1, r += base; l < r; l /= 2, r /= 2) {
            if (l & 1)
                ans = max(ans, mx[l++]);
            if (r & 1)
                ans = max(ans, mx[--r]);
        }
        return ans;
    };
    int N = n - 1;
    vector<int> b(N + 2), left(N + 2), right(N + 2), st;
    for (int i = 1; i <= N; i++)
        b[i] = depth[lca(i, i + 1)];
    for (int i = 1; i <= N; i++) {
        while (!st.empty() && b[st.back()] >= b[i])
            st.pop_back();
        left[i] = st.empty() ? 1 : st.back() + 1;
        st.push_back(i);
    }
    st.clear();
    for (int i = N; i; i--) {
        while (!st.empty() && b[st.back()] > b[i])
            st.pop_back();
        right[i] = st.empty() ? N : st.back() - 1;
        st.push_back(i);
    }
    vector<Point> p;
    for (int i = 1; i <= N; i++)
        p.push_back({left[i], right[i], right[i] - left[i] + 1, b[i]});
    bool increasing = true, decreasing = true;
    for (int i = 2; i <= N; i++) {
        if (b[i] < b[i - 1])
            increasing = false;
        if (b[i] > b[i - 1])
            decreasing = false;
    }
    int q;
    cin >> q;
    vector<int> answer(q);
    vector<Query> queries;
    for (int i = 0, l, r, k; i < q; i++) {
        cin >> l >> r >> k;
        if (k == 1)
            answer[i] = maxdepth(l, r);
        else if (increasing)
            answer[i] = b[r - k + 1];
        else if (decreasing)
            answer[i] = b[l + k - 2];
        else
            queries.push_back({l, r, k - 1, i});
    }
    if (queries.empty()) {
        for (int x : answer)
            cout << x << '\n';
        return 0;
    }
    Fenwick2D bit(N, p);
    sort(p.begin(), p.end(), [](const Point &a, const Point &b) {
        return a.len > b.len;
    });
    sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
        return a.h > b.h;
    });
    size_t at = 0;
    for (auto &z : queries) {
        while (at < p.size() && p[at].len >= z.h) {
            bit.update(p[at].l, p[at].r, p[at].value);
            ++at;
        }
        answer[z.id] = bit.query(z.r - z.h, z.l + z.h - 1);
    }
    for (int x : answer)
        cout << x << '\n';
}