LCA 的第不知道多少种求法

· · 休闲·娱乐

我发烧了。所以等我意识到我写了什么之后已经不太想删掉了。

为了解决求 LCA 的问题，我独立发现了如下两个非常重要的性质。

我突然想到，在树上找两点中间点权最小的点是一个经典问题。所以，我构建了一个树链剖分，可以在单次 O(\log^2 n) 的时间复杂度内找到一条路径上点权最小的点的位置。我们把点权设置成深度即可。

同时我们惊喜地发现，在第一次 dfs 的时候我们已经处理出来了每个点的深度，就不需要再单独去求一次了，第二次 dfs 的时候可以直接把求出来的深度放到线段树上。

然后，我们就可以在 O(n \log^2 n) 的时间内处理出 LCA 问题。下面是 DeepSeek 写的模板题 AC 代码，总用时只有五秒多。

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

const int MAXN = 5e5 + 5;
const int INF = 1e9;

int n, m, s;
vector<int> adj[MAXN];

// 树链剖分相关变量
int parent[MAXN], depth[MAXN], siz[MAXN], heavy[MAXN], top[MAXN], pos[MAXN];
int current_pos;

// 线段树相关变量
int val[MAXN], idx_pos[MAXN]; // val和idx_pos数组，pos映射到原节点
int min_val[4 * MAXN], min_idx[4 * MAXN];

// 第一次DFS，计算parent, depth, siz, heavy
void dfs1(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    siz[u] = 1;
    heavy[u] = -1;
    int max_size = 0;
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            siz[u] += siz[v];
            if (siz[v] > max_size) {
                max_size = siz[v];
                heavy[u] = v;
            }
        }
    }
}

// 第二次DFS，计算top, pos，并填充val和idx_pos
void dfs2(int u, int top_node) {
    top[u] = top_node;
    pos[u] = current_pos;
    idx_pos[current_pos] = u;
    val[current_pos] = depth[u];
    current_pos++;
    if (heavy[u] != -1) {
        dfs2(heavy[u], top_node);
        for (int v : adj[u]) {
            if (v != parent[u] && v != heavy[u]) {
                dfs2(v, v);
            }
        }
    }
}

// 构建线段树
void build(int node, int l, int r) {
    if (l == r) {
        min_val[node] = val[l];
        min_idx[node] = idx_pos[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    if (min_val[2 * node] <= min_val[2 * node + 1]) {
        min_val[node] = min_val[2 * node];
        min_idx[node] = min_idx[2 * node];
    } else {
        min_val[node] = min_val[2 * node + 1];
        min_idx[node] = min_idx[2 * node + 1];
    }
}

// 线段树区间查询，返回最小值及其索引
pair<int, int> query(int node, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) {
        return {INF, -1};
    }
    if (ql <= l && r <= qr) {
        return {min_val[node], min_idx[node]};
    }
    int mid = (l + r) / 2;
    pair<int, int> left = query(2 * node, l, mid, ql, qr);
    pair<int, int> right = query(2 * node + 1, mid + 1, r, ql, qr);
    if (left.first <= right.first) {
        return left;
    } else {
        return right;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 第一次DFS初始化
    depth[0] = -1; // 虚拟根节点的深度为-1
    dfs1(s, 0);

    // 第二次DFS初始化
    current_pos = 0;
    dfs2(s, s);

    // 构建线段树
    build(1, 0, n - 1);

    while (m--) {
        int u, v;
        cin >> u >> v;
        vector<pair<int, int>> intervals;

        // 拆分路径为多个区间
        while (top[u] != top[v]) {
            if (depth[top[u]] > depth[top[v]]) {
                swap(u, v);
            }
            intervals.emplace_back(pos[top[v]], pos[v]);
            v = parent[top[v]];
        }
        if (depth[u] > depth[v]) {
            swap(u, v);
        }
        intervals.emplace_back(pos[u], pos[v]);

        int res_val = INF;
        int res_idx = -1;

        // 查询每个区间的最小值
        for (auto &p : intervals) {
            int l = p.first;
            int r = p.second;
            auto [current_min, current_idx] = query(1, 0, n - 1, l, r);
            if (current_min < res_val || (current_min == res_val && current_idx < res_idx)) {
                res_val = current_min;
                res_idx = current_idx;
            }
        }

        cout << res_idx << "\n";
    }

    return 0;
}