倍增 & Tarjan 求解LCA

什么是LCA?

假设我们有一棵树：

1.          1
2.       /      \
3.      2         3
4.    /   \      /
5.   4    5    6

复制代码

对于 \(2\) 和 \(6\) 的LCA，就是最近公共祖先，即为距离 \(2\) 和 \(6\) 最近的两个节点公有的节点。怎么求呢？这里就有三种算法。
普通算法

我们可以把这一棵树存好，方式随便（这里展示使用邻接表），可以看到存好之后的树如下：

1. 1 - 2 - 3
2. 2 - 1 - 4 - 5
3. 3 - 1 - 6
4. 4 - 2
5. 5 - 2
6. 6 - 3

复制代码

其中 \(4,5,6\) 均为叶子节点。现在我们假设要求 \(2\) 和 \(6\) 的LCA,步骤如下：

• 首先，因为 \(6\) 的深度 \(>2\) 所以我们要 \(6\) 先跳到 \(2\) 的高度。
  
• 此时，我们的 \(6\) 节点来到了 \(3\) 节点,\(2\) 节点不变。
  
• 现在，把 \(2\) 和 \(3\) 节点同时上提。
  
• 经过一次上提之后，两个节点都来到了 \(1\) 位置。那么 \(1\) 就是 \(2\) 和 \(6\) 的LCA。
  算法实现如下：
  

[code]#include #include #include using namespace std;const int MAXN = 500010;vector tree[MAXN];int depth[MAXN];int parent[MAXN];// DFS预处理每个节点的深度和父节点void dfs(int u, int p) {    parent = p;    depth = depth[p] + 1;    for (int v : tree) {        if (v != p) {            dfs(v, u);        }    }}// 暴力方法求LCAint lca(int u, int v) {    // 将两个节点提到同一深度    while (depth > depth[v]) u = parent;    while (depth[v] > depth) v = parent[v];    // 然后一起向上找    while (u != v) {        u = parent;        v = parent[v];    }    return u;}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);        int N, M, S;    cin >> N >> M >> S;        // 建树    for (int i = 1; i < N; ++i) {        int x, y;        cin >> x >> y;        tree[x].push_back(y);        tree[y].push_back(x);    }        // 预处理    depth[0] = -1; // 根节点的父节点设为0，深度为-1+1=0    dfs(S, 0);        // 处理查询    while (M--) {        int a, b;        cin >> a >> b;        cout = depth[v]) {            u = parent[k];        }    }        // 如果此时u==v，说明v就是u的祖先    if (u == v) return u;        // 现在u和v在同一深度，一起向上找LCA    for (int k = LOG-1; k >= 0; --k) {        if (parent[k] != parent[v][k]) {            u = parent[k];            v = parent[v][k];        }    }        // 此时u和v的父节点就是LCA    return parent[0];}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);        int N, M, S;    cin >> N >> M >> S;        // 建树    for (int i = 1; i < N; ++i) {        int x, y;        cin >> x >> y;        tree[x].push_back(y);        tree[y].push_back(x);    }        // 初始化    depth[0] = -1; // 虚拟根节点的深度设为-1，这样根节点S的深度为0        // 预处理    dfs(S, 0); // 0作为虚拟父节点        // 处理查询    while (M--) {        int a, b;        cin >> a >> b;        cout  N >> M >> S;        // 建树    for (int i = 1; i < N; ++i) {        int x, y;        cin >> x >> y;        tree[x].push_back(y);        tree[y].push_back(x);    }        // 存储查询    for (int i = 0; i < M; ++i) {        int a, b;        cin >> a >> b;        // 双向存储查询        queries[a].emplace_back(b, i);        if (a != b) {            queries.emplace_back(a, i);        }    }        // 运行Tarjan算法    tarjan(S);        // 输出查询结果    for (int i = 0; i < M; ++i) {        cout