摘要: 树上倍增算法及其在最近公共祖先问题上的应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 树的直径 中我们学习了树的直径的算法，这是树上的一个基础问题，很多问题都可以拆解成树的直径问题。

树上的另一个很常见的基础问题是最近公共祖先问题，同样有很多问题需要依赖最近公共祖先的解。最近公共祖先问题是这样说的，给定一棵树，然后给定树上的两个节点，要求返回这两个节点的最近公共祖先节点。给定一棵树如果只有一次查询，那么直接通过树的遍历解决即可，如果查询有很多次，就不能每次查询都遍历了，需要想出高效的办法，主流的有树上倍增和 Tarjan 两种。

本文我们首先学习一下树上倍增的算法思想，然后以力扣 1483 题(第 193 场周赛 D 题)为模板题，讲解树上倍增法及其代码模板，此外本题还有 DFN 序的解法，也很经典，相关的概念在上一篇文章 遍历序的概念与性质 中介绍过。在本题的基础上稍微再增加一些操作，就是最近公共祖先问题的树上倍增解法，最后会简要提一下。

树上倍增

树上倍增是一种树上的常见算法，主要解决从某个节点向上找第 k 辈祖先的问题，在此基础上可以进一步解决最近公共祖先问题。此外树上倍增还可以在很多问题中有所应用。

设 $dp[u][k]$ 为节点 $u$ 往上数 $2^k$ 个祖先，也就是从 $u$ 向根节点走 $2^{k}$ 到达的节点，若该点不存在则 $dp[u][k] = 0$。$dp[u][0]$ 为 $u$ 的父节点。此外对于 $\forall k \in [1, \log n]$，有以下关系：

$$dp[u][k] = dp[dp[u][k-1]][k-1]$$

这是一个动态规划的过程，阶段是节点 $u$ 的深度。因此可以对树进行 BFS，按照层序，在节点 $u$ 入队之前，计算 $dp[u][k]$ 的值。

以上是预处理过程，时间复杂度为 $O(N\log N)$，此后可以多次对不同的节点 $u$ 求它的第 $k$ 辈祖先，过程见后面的题解。

题目

• 1483. 树节点的第 K 个祖先

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

1 <= k <= n <= 5*10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5*10^4 次

示例：

输入：
[“TreeAncestor”,”getKthAncestor”,”getKthAncestor”,”getKthAncestor”]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出：
[null,1,0,-1]

解释：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1); // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2); // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点

题解

最近公共祖先(LCA)问题的在线询问常用倍增法做，此外还有一种基于 DFN 序的思路。

算法1：树上倍增

每个节点上保存一些信息：该节点的第 k 个祖先，当 $k = 0, 1, 2, 4, 8, \cdots$ 时的祖先 id 保存下来。

即 $2^{j}$ , $j = 0, 1, 2, 3, \cdots$ 数据范围有 $n <= 5e4$, j 最大取 16 就够用。

维护预处理信息 fa[i][j] := 第 i 节点向上走 $2^[j]$ 的祖先。

考虑 getKthAncestor(i, k) 从 i 点向上跳 k 步时，可以根据 k 的二进制分解来跳。

所有的中间点和终点都可以直接查询 fa 得到。

例如跳 k = 11 步，二进制为 1011，按以下顺序跳：

• 第一位为 1 -> 先跳 1 步($2^{0}$)，到达中间点 i1。
• 第二位为 1 -> 再跳 2 步($2^{1}$)，到达中间点 i2。
• 第三位为 0 -> 当前这 4 步不跳，跳过($2^{2}$)，到达中间点 i3。
• 第四位为 1 -> 跳 8 步($2^{3}$)，到终点 u。

fa 的计算: 求 f[i][j] 时，f[i][j - 1] 已经求完，可以将 j 拆成两个 j - 1 调用结果，但是要注意一个 j - 1 就可能走到 -1 了，需要判定一下。

fa[i][0] = parent[i]
fa[0][j] = -1

若 fa[i][j - 1] = -1，则 fa[i][j] = -1
若 fa[i][j - 1] != -1，则 fa[i][j] = fa[fa[i][j - 1]][j - 1]

代码 (C++，模板)

构造函数中，给定各个节点的父节点，也就是 parent 数组，预处理 fa 的代码模板。

class TreeAncestor {
public:
    TreeAncestor(int n, vector<int>& parent) {
        // fa[i][j] := 从 i 爬 2 ^ j 步所到点的 id
        // fa[i][0] := 从 i 爬 1 不所到点的 id
        fa = vector<vector<int> >(n, vector<int>(M));
        for(int i = 0; i < n; ++i)
            fa[i][0] = parent[i];
        for(int j = 1; j < M; ++j)
            fa[0][j] = -1;
        for(int j = 1; j < M; ++j)
            for(int i = 0; i < n; ++i)
            {
                if(fa[i][j - 1] == -1)
                    fa[i][j] = -1;
                else
                    fa[i][j] = fa[fa[i][j - 1]][j - 1];
            }
    }

    int getKthAncestor(int node, int k) {
        for(int i = M - 1; i >= 0; --i)
        {
            if(k & (1 << i))
                node = fa[node][i];
            if(node == -1)
                break;
        }
        return node;
    }

private:
    const int M = 16;
    vector<vector<int> > fa;
};

算法2：DFN序

对树遍历，每到一个点，按顺序给点编一个号，该编号称为 dfn 序。

DFN 序的好的性质：任取一个子树，根节点的号是最小的，并且同一棵子树中的 dfn 序连续。

对于 getKthAncestor(i, k): 某点 i，其 dfn 序为 a，level 为 d, 要往上跳 k，则目标点的 level 为 d - k。

根据 dfn 序的两条性质，对于同一 level 中的点，包含点 i 的子树根的 dfn 序肯定小于 a，同时也是所有小于 a 的 dfn 序中最大的。

例如图中例子：a = 7, d = 4, k = 2, $d^{‘} = d - k = 2$，第二层的 dfn 序为 2, 8，其中 2 是小于 7 中的最大的，因此答案为 dfn 序为 2 对应的节点。

代码(C++)

class TreeAncestor {
public:
    TreeAncestor(int n, vector<int>& parent) {
        g = vector<vector<int> >(n);
        for(int node = 1; node < n; ++node)
            g[parent[node]].push_back(node);
        id = vector<int>(n, -1);
        nodeid = vector<int>(n, -1);
        level_dfnids = vector<vector<int>>();
        node_level = vector<int>(n, -1);
        int dfnid = 0;
        dfs(0, dfnid, 0);
    }

    int getKthAncestor(int node, int k) {
        int level = node_level[node];
        int ancestor_level = level - k;
        if(ancestor_level < 0)
            return -1;
        int dfnid = id[node];
        // 大于等于 dfnid 的最小 it
        auto it = lower_bound(level_dfnids[ancestor_level].begin(), level_dfnids[ancestor_level].end(), dfnid);
        int ancestor_dfnid = *(--it);
        return nodeid[ancestor_dfnid];
    }

private:
    vector<int> id; // nodeid -> dfnid
    vector<int> nodeid; // dfnid -> nodeid
    vector<int> node_level; // nodeid -> level
    vector<vector<int>> level_dfnids; // level -> dfnids
    vector<vector<int>> g; // 邻接表

    void dfs(int node, int& dfnid, int level)
    {
        id[node] = dfnid;
        nodeid[dfnid] = node;
        if((int)level_dfnids.size() <= level)
            level_dfnids.push_back({});
        level_dfnids[level].push_back(dfnid);
        node_level[node] = level;
        for(int son: g[node])
        {
            dfnid += 1;
            dfs(son, dfnid, level + 1);
        }
    }
};

最近公共祖先 (LCA) 问题

LCA 问题是要求节点 A, B 的最近公共祖先，需要在上题第基础上继续做。

LCA 问题一般分为两步:

第一步是将比较深的点 B 跳到与 A 同一 level，这一步刚好就是本题做的某点的第 k 个祖先。

第二步是将 A, B，同时往上跳，每次跳 $2^[k]$ 步，分别到 u1 和 u2，这里从大到小枚举 k 判断跳 $2^{k}$ 是否使得 u1 != u2，取使得 u1 != u2 的最大的 k, 因为 u1 = u2 的话，就跳到 LCA 的上面了。

重复第二步直到 A, B 的父节点相同，该父节点就是最近公共祖先。

---