https://www.luogu.com.cn/problem/P3379

P3379 【模板】最近公共祖先 (LCA)

题目描述

给定一棵包含 $N$ 个节点的有根树，共有 $M$ 次询问。每次询问给定两个节点 $x, y$，请输出它们的最近公共祖先（Lowest Common Ancestor, LCA）。

最近公共祖先的定义：对于有根树 $T$ 的两个节点 $x, y$，最近公共祖先 $LCA(x, y)$ 表示一个节点 $u$，满足 $u$ 是 $x$ 和 $y$ 的祖先且 $u$ 的深度尽可能大。

---

输入格式

第一行包含三个整数 $N, M, S$，分别表示树的节点数、询问次数和树根结点的编号。 接下来 $N-1$ 行，每行包含两个整数 $x, y$，表示节点 $x$ 和节点 $y$ 之间有一条无向边。 接下来 $M$ 行，每行包含两个整数 $a, b$，表示询问节点 $a$ 和节点 $b$ 的最近公共祖先。

输出格式

输出共 $M$ 行，每行包含一个整数，对应每次询问的结果。

---

输入输出样例

样例 1

输入：

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出：

4
4
1
4
4

---

数据范围与提示

• $1 \le N, M \le 5 \times 10^5$
• $1 \le S \le N$
• 节点编号范围：$1 \le x, y \le N$
• 边数固定为 $N-1$，保证构成一棵树。
• 注意：由于数据规模巨大，建议使用快速读入（Fast I/O）并将深度优先搜索（DFS）改为非递归形式或手动扩大系统栈空间，以防止爆栈（Stack Overflow）。

---

1. 预备知识点

• 树的存储：邻接表（std::vector 或 链式前向星）。
• 倍增算法 (Binary Lifting)：利用二进制拆分思想，将 $O(N)$ 的向上跳跃优化为 $O(\log N)$。
• 深度优先搜索 (DFS)：预处理每个节点的深度 depth 和父节点。
• 动态规划 (DP)：倍增数组的初始化过程本质是 DP。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：朴素想法的局限性

如果我们要求节点 $x$ 和 $y$ 的最近公共祖先：

1. 先让深度较深的点（假设是 $x$）向上跳，直到与 $y$ 同深。
2. 然后 $x$ 和 $y$ 同时向上一步步跳，直到相遇。

• 复杂度分析：单次询问最坏 $O(N)$。对于 $5 \times 10^5$ 次询问，总复杂度 $O(NM)$，必然超时。

第二步：利用“倍增”实现瞬移

我们不再一步步跳，而是以 $2^k$（$1, 2, 4, 8, \dots$）步跳。

• 状态定义：fa[u][k] 表示节点 $u$ 向上跳 $2^k$ 步到达的祖先。
• 状态转移：跳 $2^k$ 步等于先跳 $2^{k-1}$ 步，再跳 $2^{k-1}$ 步。 fa[u][k] = fa[fa[u][k-1]][k-1]

第三步：查询逻辑的重构

1. 对齐深度：利用二进制拆分（类似快速幂思想），让深的点快速跳到与浅的点同深。
2. 同步跳跃：如果两点已经重合，说明浅的点就是 LCA。否则，从大到小尝试跳 $2^k$ 步。如果跳完后两点不相等，说明还没跳过头，可以放心地跳上去；如果相等，说明跳到了共同祖先或更高位置，此时不跳，减小 $k$ 继续试。
3. 最终结果：跳完后，$x$ 和 $y$ 的父节点即为 LCA。

---

3. 算法逻辑流程图 (Mermaid)

预处理部分 (Preprocessing)

graph TD
    A["开始 读入树信息"] --> B["构建邻接表或链式前向星"]
    B --> C["从根节点 S 开始 DFS"]
    C --> D["计算 depth 和 fa{u}{0}"]
    D --> E["循环 k 从 1 遍历到 20"]
    E --> F["循环 u 从 1 遍历到 N"]
    F --> G["DP转移 fa{u}{k} = fa{fa{u}{k-1}}{k-1}"]
    G --> F
    F -- "节点遍历完" --> E
    E -- "幂次循环完" --> H["预处理结束"]

查询部分 (Query)

graph TD
    I["输入询问点 x 和 y"] --> J{"depth x 小于 depth y ?"}
    J -- "是" --> K["交换 x 和 y"]
    J -- "否" --> L["计算深度差 delta"]
    K --> L
    L --> M["利用倍增将 x 向上跳 delta 距离使深度相等"]
    M --> N{"此时 x 等于 y ?"}
    N -- "是" --> O["输出 x 为 LCA"]
    N -- "否" --> P["循环 k 从 20 递减到 0"]
    P --> Q{"fa{x}{k} 不等于 fa{y}{k} ?"}
    Q -- "是" --> R["x = fa{x}{k} 且 y = fa{y}{k}"]
    Q -- "否" --> P
    R --> P
    P -- "循环结束" --> S["输出 fa{x}{0} 为 LCA"]

---

4. 读题关键词与坑点总结

1. “无向边”：存图时需要双向加边，数组空间（尤其是邻接表）要开 $2 \times N$。
2. “5e5” 数据规模：
   • 时间复杂度必须控制在 $O((N+M)\log N)$ 左右。
   • cin / cout 会极大拖慢速度，必须使用 scanf / printf 或自定义 getchar 快读。
   • 递归 DFS 在 $5 \times 10^5$ 深度下会导致系统栈崩溃。
3. “最近”：同步跳跃时，之所以判 fa[x][k] != fa[y][k] 是为了保证我们一直停留在 LCA 的下方一层，这样最终输出 fa[x][0] 才是“最近”。

---

5. 复杂度分析思考过程

• 时间复杂度：
  • 预处理（DFS + 倍增表）：$O(N \log N)$。
  • 单次查询：$O(\log N)$（二进制跳跃）。
  • 总时间：$O(N \log N + M \log N)$。
• 空间复杂度：
  • 邻接表：$O(N)$。
  • 倍增表 fa[N][20]：$O(N \log N)$。
  • 对于 $N=5 \times 10^5$，倍增数组约占 $5 \times 10^5 \times 20 \times 4$ 字节 $\approx 40$ MB，完全符合 NOI 的 256MB 或 512MB 限制。

---

6. 时间复杂度优化建议

• 常数优化：可以使用位运算 (1 << k) 替代幂函数。
• ST 表优化：利用欧拉序列（Euler Tour）将 LCA 转化为 RMQ 问题，预处理 $O(N \log N)$，查询可以达到真正的 $O(1)$。但在 NOI 中，倍增算法通常已足够通过且代码实现更稳健。
• Tarjan 离线算法：利用并查集将复杂度进一步压缩至 $O(N + M \alpha(N))$，适合处理超大规模且无需即时返回结果的情况。