问题分析

给定一棵 $n$ 个节点的有根树，每个节点只能向其父节点移动。有 $m$ 次询问，每次询问两个节点 $A$ 和 $B$，求它们能够相遇的最近汇合点。

关键约束：每个节点只能向上走（向父亲方向移动）。

数学模型

设：

• $depth[u]$ 表示节点 $u$ 的深度（根节点深度为 0 或 1）
• $ancestor(u, d)$ 表示节点 $u$ 向上走 $d$ 步到达的祖先

对于两个节点 $A$ 和 $B$：

1. 它们只能在某个公共祖先处相遇
2. 由于只能向上走，汇合点必须是 $A$ 和 $B$ 的公共祖先
3. 要找到最近的汇合点，即深度最大的公共祖先

解决方案

这就是经典的**最近公共祖先（LCA）**问题。

我们需要快速回答 $m$ 次 LCA 查询，$n \leq 900000$，$m \leq 100000$。

算法选择

有以下几种常见的 LCA 算法：

1. 倍增法：预处理每个节点向上 $2^k$ 级的祖先

   • 预处理 $O(n \log n)$，查询 $O(\log n)$
   • 空间 $O(n \log n)$
   • 适合本题数据规模

2. Tarjan 离线算法：一次性处理所有查询

   • 预处理 $O(n + m\alpha(n))$，接近线性
   • 但需要离线处理所有查询

3. 树链剖分：预处理 $O(n)$，查询 $O(\log n)$

   • 常数较小，实现相对简单

由于 $n$ 较大但 $m$ 适中，倍增法和树链剖分都可以。考虑到实现简洁性，推荐倍增法。

倍增法实现细节

预处理

1. 读入树结构，建立父子关系
2. 计算每个节点的深度 $depth[u]$
3. 计算倍增表 $up[u][k]$ 表示节点 $u$ 向上 $2^k$ 步的祖先

查询 LCA(a, b)

1. 如果 $depth[a] < depth[b]$，交换 $a$ 和 $b$
2. 将 $a$ 向上提升到与 $b$ 同一深度
3. 如果此时 $a = b$，则 $a$ 就是 LCA
4. 否则，从最大 $k$ 开始向下尝试，将 $a$ 和 $b$ 同时向上提，直到 $a$ 和 $b$ 的父亲相同
5. 返回 $a$ 的父亲

时间复杂度

• 预处理：$O(n \log n)$
• 每次查询：$O(\log n)$
• 总复杂度：$O(n \log n + m \log n)$，在给定数据范围内可行

C++ 实现

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

const int MAXN = 900005;
const int LOG = 20; // 2^20 > 900000

int n, m;
vector<int> children[MAXN];
int parent[MAXN];
int depth[MAXN];
int up[MAXN][LOG];

void dfs(int u, int p) {
    parent[u] = p;
    depth[u] = depth[p] + 1;
    
    // 初始化倍增表
    up[u][0] = p;
    for (int i = 1; i < LOG; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    
    // 递归处理子节点
    for (int v : children[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

int lca(int a, int b) {
    // 确保 a 更深
    if (depth[a] < depth[b]) swap(a, b);
    
    // 将 a 提升到与 b 同一深度
    int diff = depth[a] - depth[b];
    for (int i = LOG-1; i >= 0; i--) {
        if (diff & (1 << i)) {
            a = up[a][i];
        }
    }
    
    // 如果已经是同一个节点
    if (a == b) return a;
    
    // 同时向上提升
    for (int i = LOG-1; i >= 0; i--) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    
    // 此时 a 和 b 的父亲是 LCA
    return up[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    
    // 读取父子关系，题目保证父亲编号小于自身
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        children[p].push_back(i);
        children[i].push_back(p); // 双向边便于DFS
    }
    
    // 预处理
    depth[0] = -1; // 虚拟根节点的深度设为-1，使得根节点深度为0
    dfs(1, 0); // 假设根节点是1
    
    // 处理查询
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << "\n";
    }
    
    return 0;
}

算法标签

• 最近公共祖先（LCA）
• 树上倍增
• 树的基本操作
• 预处理与查询

注意事项

1. 题目保证每个点的父亲小于它本身，因此根节点是 1
2. 深度计算可以根据需求调整为从 0 或 1 开始
3. 对于 $n=900000$，$LOG=20$ 足够（$2^{20}=1048576$）
4. 使用邻接表存储树结构，避免爆栈可以改用迭代 DFS 或 BFS