2302. 最近公共祖先【模板】
1000ms
256MB
简单
模板题
题目描述
在一棵由 $N$ 个节点（编号为 $1 \sim N$）构成的有根树上，已知根节点为 $S$。有 $M$ 次询问，每次询问给定两个节点 $x$ 和 $y$，你需要求出它们的最近公共祖先（Lowest Common Ancestor, LCA）。
最近公共祖先的定义：对于有根树 $T$ 的两个节点 $x, y$，最近公共祖先 $LCA(x, y)$ 表示一个节点 $u$，满足 $u$ 是 $x, y$ 的祖先且 $u$ 的深度尽可能大（即距离根节点最远）。
输入格式
- 第一行包含三个正整数 $N, M, S$ ($1 \le N, M \le 5 \times 10^5, \quad 1 \le S \le N$)，分别表示节点数、询问次数和根节点编号。
- 接下来 $N - 1$ 行，每行包含两个正整数 $u, v$ ($1 \le u, v \le N$)，表示节点 $u$ 和节点 $v$ 之间有一条无向边相连。
- 接下来 $M$ 行，每行包含两个正整数 $x, y$ ($1 \le x, y \le N$)，表示一组询问。
输出格式
- 输出共 $M$ 行，每行包含一个整数，表示对应询问的最近公共祖先的节点编号。
样例 1
输入 (Input)
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
输出 (Output)
4 4 1 4 4
- 对于 $30\%$ 的数据：$N, M \le 1000$。
- 对于 $100\%$ 的数据：$1 \le N, M \le 5 \times 10^5$，$1 \le S \le N$，并且输入的图保证是一棵树。
- **算法提示**：
由于 $N$ 和 $M$ 的范围达到了 $5 \times 10^5$，使用普通的暴力向上标记法在最坏情况下时间复杂度为 $O(N)$，总时间复杂度为 $O(NM)$，会导致运行超时（TLE）。
建议使用**树上倍增算法（Doubling LCA）**或 **Tarjan离线算法**，使得单次查询的平均时间复杂度降低至 $O(\log N)$ 或 $O(1)$。
- **I/O 优化**：本题输入输出量非常大，在 C++ 中请务必使用快速读入或者 `cin.tie(0)` 优化。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功