【图论】树的最近公共祖先

更新于 分类于 ， 阅读次数： 本文字数： 4.6k 阅读时长 ≈ 4 分钟

树的最近公共祖先（LCA）问题

概念和记法

  • LCA(S)LCA(S) 是点集SS 的最近公共祖先
  • uu 是vv 的祖先⇔LCA(u,v)=u\Leftrightarrow LCA(u,v)=u
  • LCA(A∪B)=LCA(LCA(A),LCA(B))LCA(A\cup B)=LCA(LCA(A),LCA(B)) ，A,BA,B 是点集
  • 在树上任选三点u1,u2,u3,LCA(u1,u2),LCA(u1,u3),LCA(u2,u3)u_1,u_2,u_3,LCA(u_1,u_2),LCA(u_1,u_3),LCA(u_2,u_3) 中一定有两个是相等的。
  • 设d(u,v)d(u,v) 是uu 到vv 的最短距离，h(u)h(u) 是深度，有d(u,v)=h(u)+h(v)−2×h(LCA(u,v))d(u,v)=h(u)+h(v)-2\times h(LCA(u,v)) ，很好理解，画个图就行
  • 后续内容用fa[i] 相关的表示记录ii 节点的父亲节点

朴素算法

  • 预处理深度，深度高的先跳直到相同深度，然后一起往上跳直到相遇，预处理父亲节点O(n)O(n) ，单次查询O(n)O(n) ，但这个查询复杂度一般都无法接受

倍增改进

预处理出fa[x][i]fa[x][i] 表示xx 的第2i2^i 个祖先，跳的时候从ii 大到小看fa[u][i]fa[u] [i] 和fa[v][i]fa[v] [i] ，除非相等或为00 ，否则跳上去。

预处理O(nlog⁡n)O(n\log n) ，单次查询O(log⁡n)O(\log n) 。

带权（求x, y距离），如果不带权去掉cost数组的处理就可以了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<node> tree[N];
int fa[N][31], cost[N][31], dep[N];
//fa[x][i]是x的第2^i个祖先节点，cost[x][i]是x到第2^i个祖先节点的长度
void dfs(int rt, int from) //预处理
{
    fa[rt][0] = from; // 初始化：第2^0 = 1个祖先就是它的父亲节点，dep 更新
    dep[rt] = dep[from] + 1;
    for (int i = 1; i < 31; ++i)
    {
        fa[rt][i] = fa[fa[rt][i - 1]][i - 1]; //第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第2^(i-1) 的祖先节点
        cost[rt][i] = cost[fa[rt][i - 1]][i - 1] + cost[rt][i - 1];
    }
    for (auto it : tree[rt])
    {
        if (it.to == from)
            continue;
        cost[it.to][0] = it.val;
        dfs(it.to, rt);
    }
}
int lca(int x, int y) //求x,y的距离
{
    if (dep[x] > dep[y])
        swap(x, y);                     //y比x深度大
    int tmp = dep[y] - dep[x], ans = 0; //先跳深度差
    for (int i = 0; tmp; i++, tmp >>= 1)
        if (tmp & 1) //长的像快速幂，跳的是深度差（二进制）1的个数
            ans += cost[y][i], y = fa[y][i];
    if (y == x)
        return ans;                         //x=y，则这就是他们的公共祖先了
    for (int i = 30; i >= 0 && y != x; --i) //否则一起往上跳，优先跳大的
        if (fa[x][i] != fa[y][i])           //跳到lca下面，再往上跳
        {
            ans += cost[x][i] + cost[y][i]; //累加
            x = fa[x][i];
            y = fa[y][i];
        }
    ans += cost[x][0] + cost[y][0];
    // LCA是fa[x][0]=fa[y][0]=x=y，这里返回的是距离
    return ans;
}

离线：tarjan

dfs整棵树：

遍历过程中先将当前节点看作根节点，标记已访问，递归访问子节点；

回溯时，更新子节点的并查集，并遍历所有关于当前节点的查询，如果另一个节点已经访问过，就记录答案为另一个节点的父亲节点，这是因为回溯过的点的父亲节点一定不会超过lca（感觉代码+想象回溯过程更好理解一点）。

代码中用前向星建树，用前向星记录每个节点的询问（偶数编号+奇数编号建无向边，方便答案的输出，是图的基本概念那节建图部分提过的技巧）。

预处理O(n)O(n) ，所有询问O(n+m)O(n+m) ，但常数大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int n, m, s;
int fa[N]; //并查集
bool vst[N];
int tot;
int lca[N << 1];
struct Edge
{
    int to, nxt;
} edge[N << 1], query[N];
int head[N], qhead[N];
void add_edge(int u, int v)
{
    edge[tot].to = v;
    edge[tot].nxt = head[u];
    head[u] = tot;
    tot++;
}
void add_query(int u, int v)
{
    query[tot].to = v;
    query[tot].nxt = qhead[u];
    qhead[u] = tot;
    tot++;
}
int father(int x)
{
    return fa[x] == x ? x : fa[x] = father(fa[x]);
}
void tarjan(int rt)
{
    vst[rt] = true;
    for (int i = head[rt]; ~i; i = edge[i].nxt)
        if (!vst[edge[i].to])
        {
            tarjan(edge[i].to);
            fa[edge[i].to] = rt; //回溯时将下面节点的并查集更新
        }
    for (int i = qhead[rt]; ~i; i = query[i].nxt)
        if (vst[query[i].to]) //回溯时更新所有节点的lca，即回溯的时候并查集的顶端必然不会超过lca
            lca[i ^ 1] = lca[i] = father(query[i].to);
}
int main()
{
    read(n), read(m), read(s);
    for (int i = 1; i <= n; i++)
        head[i] = qhead[i] = -1;
    int u, v;
    for (int i = 1; i < n; i++)
    {
        read(u), read(v);
        add_edge(u, v);
        add_edge(v, u);
    }
    tot = 0;
    for (int i = 0; i < m; i++)
    {
        read(u), read(v);
        add_query(u, v);
        add_query(v, u);
    }
    for (int i = 1; i <= n; i++)
        fa[i] = i; //初始化并查集
    tarjan(s);
    for (int i = 0; i < m; i++)
        printf("%d\n", lca[i << 1]);
    return 0;
}

在线：欧拉序列RMQ

  • 欧拉序列：树上dfs时，第一次访问和回溯的时候记录节点编号形成的长2n−12n-1 的序列，记为dfn[dfntot]=rtdfn[dfntot]=rt
  • 时间戳：第一次出现或是最后一次出现的时间（序列位置）pos[rt]=dfntotpos[rt]=dfntot
  • 从uu 走到vv 经过的深度最小的结点就是LCA(u,v)LCA(u,v)
  • 求欧拉序O(n)O(n) ，st表预处理O(nlog⁡n)O(n\log n) ，查询O(1)O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int dfn[N << 1], dep[N << 1], pos[N];
//dfn[i]=x表示欧拉序列第i位是x节点，dep[i]=x表示欧拉序列第i位的这个节点深度是x，pos[i]=x表示i节点第一次出现在在欧拉序列里的位置是x
int dfntot; //欧拉序列总数
void dfs(int rt, int from, int depth)
{
    dfn[++dfntot] = rt;
    pos[rt] = dfntot;
    dep[dfntot] = depth;
    for (int i = head[rt]; ~i; i = edge[i].nxt)
    {
        int to = edge[i].to;
        if (to == from)
            continue;
        dfs(to, rt, depth + 1);
        dfn[++dfntot] = rt;
        dep[dfntot] = depth;
    }
}
int lg[N << 1];
int st[N << 1][25];
void init_log() // 预处理 lg 代替库函数 log2 来优化常数
{
    lg[0] = lg[1] = 0;
    for (int i = 2; i <= dfntot; i++)
        lg[i] = lg[i >> 1] + 1;
}

void init_st() //初始化st表，存的是欧拉序区间中深度最小的dfn序值
{
    for (int i = 1; i <= dfntot; i++)
        st[i][0] = i;
    for (int j = 1; j < 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= dfntot; i++)
            st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]] ?
                       st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
int RMQ(int x, int y) //查询公共祖先
{
    x = pos[x], y = pos[y]; //节点第一次出现的dfn
    if (y < x)
        swap(x, y);
    int k = lg[y - x + 1];
    x = st[x][k], y = st[y - (1 << k) + 1][k]; //RMQ基操
    return dfn[dep[x] < dep[y] ? x : y];
}