最近公共祖先 - lzl's blog

向上标记法#

1
// 第一次dfs标记根节点的该结点之间所有点
2
bool dfs(int cur, int fa, int val) {
3
    if (cur == val) {
4
        id[cur] = true;
5
        return true;
6
    }
7
    for (int i = h[cur]; ~i; i = ne[i]) {
8
        int v = e[i];
9
        if (v == fa) continue;
10
        if (dfs(v, cur, val)) {
11
            id[cur] = true;
12
            return true;
13
        }
14
    }
15
    return false;
16
}
17
// 第二次dfs遇到有标记的点就是lca(a,b)
18
int redfs(int cur, int fa, int val) {
19
    if (cur == val) {
20
        if (id[cur]) return cur;
21
        return -1;
22
    }
23
    for (int i = h[cur]; ~i; i = ne[i]) {
24
        int v = e[i];
25
        if (v == fa) continue;
26
        int t = redfs(v, cur, val);
27
        if (t > 0) return t;
28
        else if (t == -1) {
29
            if (id[cur]) return cur;
30
            return -1;
31
        }
32
    }
33
    return 0;
34
}

倍增法#

预处理 $O(nlogn)$

$f[i,k]$ ：结点 $i$ 的第 $2^k$ 个祖先 $0 \le k \le logn$ ，其中 $n$ 是结点的数量，注意下标从 $1$ 开始，因为这样方便结点 $0$ 充当一个虚拟最大祖先，也就是哨兵的意思
$depth[i]$ 表示结点 $i$ 的深度，注意 $depth[i]>0$ ，因为这样方便 $\forall i, depth[i] > depth[0]$

根据预处理求结点 $x$ 的第 $k$ 个祖先对 $k$ 进行二进制拆分： $k = 2^{a_1}+2^{a_2}+\cdots+2^{a_j}$ ，因此求 $x$ 的第 $k$ 个祖先就是 $f(f(f(x,a_1),a_2) \cdots , a_j)$

求 $lca(x,y)$ $O(logn)$

对齐深度，把深度较高的点，假设为 $x$ ，找到 $x$ 的第 $depth[x]-depth[y]$ 个祖先结点 $x^\prime$ ，这样就对齐了两点的深度。
同样地，利用二进制拆分将 $x^\prime,y$ 移动到 $lca(x,y)$ 的下一个结点，最终再将变化后的 $x^\prime$ 或 $y$ 再往上跳一格，也就是 $f[x^\prime][0]$ 就是最近公共祖先

代码如下：

1
/*
2
dfs调用: dfs(r, 0, 1)
3
*/
4
int h[N], e[N << 1], ne[N << 1], idx = 0;
5
int f[N][18], dep[N];
6
int n, r, tot = 0;
7

8
void dfs(int u, int fa, int cur) {
9

10
    dep[u] = cur;
11
    f[u][0] = fa;
12
    for (int i = 1; i < 18; i ++ )
13
        f[u][i] = f[f[u][i - 1]][i - 1];
14
    for (int i = h[u]; ~i; i = ne[i]) {
15
        int v = e[i];
16
        if (v == fa) continue;
17
        dfs(v, u, cur + 1);
18
    }
19
}
20
// bfs 预处理更加保险，不会爆栈
21
void bfs() {
22
    queue<int> Q;
23
    Q.push(r);
24
    dep[r] = 1;
25
    st[r] = true;
26

27
    while (Q.size()) {
28
        int u = Q.front(); Q.pop();
29
        for (int i = h[u]; ~i; i = ne[i]) {
30
            int v = e[i];
31
            if (st[v]) continue;
32
            dep[v] = dep[u] + 1;
33
            f[v][0] = u;
34
            for (int i = 1; i < 18; i ++ )
35
                f[v][i] = f[f[v][i - 1]][i - 1];
36
            Q.push(v);
37
            st[v] = true;
38
        }
39
    }
40
}
41

42
int lca(int x, int y) {
43

44
    if (dep[x] > dep[y]) swap(x, y);
45
    for (int i = 17; i >= 0; i -- )
46
        if (dep[f[y][i]] >= dep[x])
47
            y = f[y][i];
48

49
    if (x == y) return x;
50
    for (int i = 17; i >= 0; i -- )
51
        if (f[x][i] != f[y][i])
52
            x = f[x][i], y = f[y][i];
53
    return f[x][0];
54
}

tarjan 离线算法#

离线算法和在线算法#

离线算法：一般的面向有多次询问的题面，然后一次性把所有询问读入，然后再输出结果的算法在线算法：即问即答

tarjan 求 lca#

如图所示：在 dfs 的过程中访问到某点时我们可以将点分为三类，其中蓝色的点表示已经访问完的点，绿色的点相当于在递归栈中的点，也就是正在访问的点，白色的点表示未尚未标记的点。

根据这样对点进行划分，有一个结论：如果要求两个点的最近公共祖先，其中一个点在已经访问完的点中，一个点就是当前正在访问的点，那么这些点对的最近公共祖先一定是绿色集合中的点。为此，可以提前将所有询问存储，进而设计一个一次遍历整棵树的同时回答所有询问的离线算法。

算法流程：

首先存储所有询问，存储方式类似于 vector 写法的邻接表，query[i] 存储所有与点 $i$ 相关的查询与其查询索引
然后从任意一个点做 tarjan 算法 2.1 首先遍历当前点的所有孩子，然后遍历完利用并查集把当前孩子的双亲设置为当前结点 2.2 利用并查集求解与这个点所有相关的，另外一个点是已经访问完的所有询问d 2.3 将当前结点标记为已经访问完的状态代码如下：

1
int h[N], e[M], ne[M], idx = 0;
2
int st[N], fa[N];
3
vector<PII> query[M];
4
int lca[M];
5
int n, m;
6

7
void tarjan(int u) {
8

9
    st[u] = 1;
10
    for (int i = h[u]; ~i; i = ne[i]) {
11
        int v = e[i];
12
        if (st[v]) continue;
13
        tarjan(v);
14
        fa[v] = u;
15
    }
16
    for (auto [v, id]: query[u])
17
        if (st[v] == 2)
18
            lca[id] = get(v);
19
    st[u] = 2;
20
}

向上标记法#

倍增法#

tarjan 离线算法#

离线算法和在线算法#

tarjan 求 lca#

RMQ 求 lca#