小指针

V1

2022/09/15阅读:39主题:凝夜紫

【图论专题】最近公共祖先问题的算法思路与应用

外部链接公众号无效,点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

最近公共祖先问题

最近公共祖先,又叫LCA问题。在一个有根树当中,如果节点z既是x的祖先,又是节点y的祖先,那么就称z为x和y的公共祖先,而所有公共祖先中,深度最大的一个称为最近公共祖先,记为LCA(x,y) 图中黄色圈为x和y的公共祖先,而深度最大的那个即为最近公共祖先

特别要说明的,每个点自己也可能是自己的祖先,也就是说,假如x是y的祖先,那么就会有LCA(x,y)=x

向上标记法

用向上标记法可以求解出两个点的最近公共祖先。我们从一个点x向上遍历所有点,把能到达的祖先节点都标记上,再从另一个点y出发向上遍历,碰到的第一个被标记的点,就是LCA(x,y)。

从算法描述中,也可以看出来,这个方法是O(n)复杂度的(最坏情况遍历所有点),因此不常用,比较常用的是另外一个方法--倍增法。

倍增法

预处理fa数组

预处理出数组fa[i,j],用来表示从节点i开始,向上走 步所到达的那个节点。

对于示例中的图示,以节点7开始向上走,则fa数组如下:

  1. fa[7, 0]=4:表示向上走 步,到达点4;
  2. fa[7, 1]=2:表示向上走 步,到达点2;
  3. fa[7, 2]=0:表示向上走 步,到达一个不存在的点;

那么如何快速求出fa[i,j]呢?可以分两种情况套路:

  1. 当j=0时,fa[i,j]=i的父节点;

  2. 当j>0时,可以走两个fa[i,j-1],诶?这是什么意思呢?

    其实就是二次幂的计算形式,假如当前j=2,则有 ;那么下一步就是j=3,则有 ;那么需要8通过 来计算吗?显然是不需要的,因为我们可以把 拆解成 ,这时候我们神奇的发现,在上一步我们已经把 计算出来了,所以我们就把计算 转换成了两个

    用公式表示就是:fa[i,j]=fa[ fa[i,j-1], j-1]

    那这个求公式就比较明显的是一个迭代的过程了,用DFS或者BFS就可以了,如此,我们就求出了fa数组。

预处理depth数组

预处理出数组depth[i],顾名思义,用来表示深度或者叫层数。 这个数组就比较明显了,其实就是每个点i到根节点的距离加一。比如:1号点到根节点的距离为0,加1就是1;2号点到根节点距离为1,加1就是2;4号点到根节点距离为2,加1就是3,依次类推;

求LCA

  1. 先将深度较深的那个点跳到与深度较浅的那个点的同一层

  2. 让两个点同时向上跳,一直跳到他们的最近公共祖先的下一层

    为什么要跳到下一层,而不是直接跳到最近公共祖先呢?

    是因为方便进行判断,如果直接跳到最近公共祖先,则要用fa[a, k]==fa[b, k],那么此时,我们是没有办法去判断这个最近公共祖先是否是最近的。

    如果是判断最近公共祖先的下一层,那么就可以在fa[a, k]!=fa[b, k]的时候进行循环,当循环停止的时候代表他们的上一层就是最近公共祖先。

时间复杂度

在预处理中,遍历所有的点是O(n)的,对于每个点还要求出fa数组,这个过程是O(logn)的,所以最终复杂度是是O(nlogn)的。

查询是O(logn)。

Tarjan--离线求LCA

离线算法:对于有多个询问的问题,将所有的询问都读入进来之后,再对所有的询问给出答案;

在线算法:对于有多个询问的问题,读入一个询问,给出一个询问的答案。

在使用向上标记法的过程(BFS或者DFS)中,将所有的点分成三类:

  1. 已经遍历过并且回溯过的点,回溯过的意思就是这些点和它的父子节点等等全部都搜索完成了,这些点标记成2
  2. 正在搜索的分支,也就是当前递归栈中的所有点,这些点标记成1
  3. 还未搜索到的点,这些点标记为0

对于当前正在搜索的点x,我们找到与它相关的询问,假设与x相关的询问是{x,y},如果y是属于绿色区域2的,那么在图中,我们可以直观的感受到,LCA(x, y)就是z。

进一步的,我们神奇的发现z的所有子节点与x的最近公共祖先都是z,依次类推,红色区域中,z的所有子节点(z1,z2...) 的所有子节点 与x的最近公共祖先都是(z1,z2...)它们自己

所以,这就启发我们,可以把 绿色区域中的节点 全部合并到 处于红色区域中 它们各自的根节点(z,z1,z2...) 上去。这样做之后,想知道x与绿色区域中任意一点y的最近公共祖先,其实就是看点y目前处于哪一个集合中

合并集合这个操作,我们可以使用并查集

这种做法每个点只被遍历一次,也只会被合并一次以及查询一次,因此这种做法的时间复杂度是O(n+m)。

AcWing 1172. 祖孙询问

给定一棵包含 n 个节点的有根无向树,节点编号互不相同,但不一定是 1∼n。

有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。

输入格式
输入第一行包括一个整数 表示节点个数;

接下来 n 行每行一对整数 a 和 b,表示 a 和 b 之间有一条无向边。如果 b 是 −1,那么 a 就是树的根;

第 n+2 行是一个整数 m 表示询问个数;

接下来 m 行,每行两个不同的正整数 x 和 y,表示一个询问。

输出格式
对于每一个询问,若 x 是 y 的祖先则输出 1,若 y 是 x 的祖先则输出 2,否则输出 0。

数据范围

1≤n,m≤4×10^4,
1≤每个节点的编号≤4×10^4

输入样例

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例

1
0
0
0
2

题目描述

给出一颗有根树,给m个询问,每个询问是x与y的祖孙关系。

题目分析

本题是最近公共祖先的模板题,使用上面我们分析出来的倍增法进行解决即可。

Code

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = 80010;
// 每个点最多跳2^15 所以0~15总共16个数
int depth[N], fa[N][16];
int h[N], e[M], ne[M], idx;
int n, m;
int q[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root) {
    memset(depth, 0x3fsizeof depth);
    q[0] = root;
    int hh = 0, tt = 0;
    // 深度数组depth中 我们将一个不存在的点0当做哨兵
    // 哨兵的好处 就是 当深度跳出了树的时候 可以不用特殊处理
    // (详见后面的注释)
    depth[0] = 0, depth[root] = 1;
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k < 16; k ++ ) {
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
                }
            }
        }
    }
}

int lca(int a, int b) {
    // 第一步 保证从深度大的开始往上找
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k -- ) {
        // 将两个点的深度调整到一致
        // 注意这里就体现了哨兵的作用
        // 当depth跳出去的时候就是0
        // 任何一个有效的深度都大于0 
        // 所以当跳出去之后这里就自动不成立
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    }
    if (a == b) return a;
    // 第二步 两个点一起往上找 直到最近公共祖先的下一个
    for (int k = 15; k >= 0; k -- ) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    // 最后他们的父节点就是最近公共祖先
    return fa[a][0];
}

int main() {
    cin >> n;
    int root = 0;
    memset(h, -1sizeof h);
    for (int i = 0; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
        if (b == -1) root = a;
        add(a, b); add(b, a);
    }
    cin >> m;
    bfs(root);
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }
    return 0;
}

AcWing 1171. 距离

给出 n 个点的一棵树,多次询问两点之间的最短距离。

注意:

  1. 边是无向的。
  2. 所有节点的编号是 1,2,…,n。

输入格式
第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;

下来 n−1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k;

再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式
共 m 行,对于每次询问,输出一行询问结果。

数据范围

2≤n≤10^4,
1≤m≤2×10^4,
0<k≤100,
1≤x,y≤n

输入样例1

2 2 
1 2 100 
1 2 
2 1

输出样例1

100
100

输入样例2

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2

10
25

题目描述

给定一棵树,询问树上两点之间的最短距离

题目分析

求树上两点间的距离,通常可以使用一个小技巧,我们先求出每个点到根节点的距离,记作d数组,那么两个点x和y的距离就是d[x]+d[y]-2*d[lca(x,y)] 如图,想求x和y之间的距离

x到根节点的距离d[x]等于绿色加蓝色,y到根节点的距离d[y]等于黄色加蓝色,而蓝色部分表示的就是LCA(x,y)=p到根节点的距离,这段距离d[p]被加了两次是无效的,所以要去掉。总结起来就得到了上面的公式。

所以这题的主要部分就变成了求两个点的最近公共祖先是谁

Code

本题的实现主要展示tarjan--LCA模板

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

typedef pair<intint> PII;

const int N = 20010, M = N * 2;
int h[N], e[M], ne[M], w[M], idx;
int p[N]; // 并查集数组
int res[N]; // 查询编号对应的结果
int st[N]; // 标记点的区域
int dist[N];
vector<PII> query[N]; // 存储查询的另一个点和查询编号
int n, m;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化dist数组,每个点到根节点的距离
void dfs(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        // 当前点j到根节点的距离 
        // 等于 父节点到根节点距离 加上 父节点到它的距离
        dist[j] = dist[u] + w[i];
        dfs(j, u); // 递归搜u的所有子节点。
    }
}

// 并查集函数
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// tarjan LCA 算法模板
void tarjan(int u) {
    st[u] = 1// 标记u为当前正在搜索的点
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        // 如果子节点不在区域0
        if (!st[j]) {
            tarjan(j); // 递归处理子节点
            p[j] = u; // 将子节点合并到父节点u上
        }
    }
    // 处理 所有和 当前节点u相关的查询
    for (auto item: query[u]) {
        int y = item.first, id = item.second;
        // 如果另一个节点y 已经处于绿色区域(2号区域)
        // 那么关于它的LCA(y, u) 就是它在并查集中的集合编号
        if (st[y] == 2) {
            int p = find(y); // LCA(y, u)
            res[id] = dist[u] + dist[y] - dist[p] * 2// 公式计算距离
        }
    }
    st[u] = 2// 当前节点已经完全遍历过
}

int main() {
    cin >> n >> m;
    memset(h, -1sizeof h);
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        cin >> a >> b;
        // a与b不想等才需要查询如果相等距离就是0 而res默认为0
        if (a != b) {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    dfs(1-1);
    tarjan(1);
    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);
    return 0;
}

AcWing 352. 闇の連鎖

传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。

经过研究,你发现 Dark 呈现无向图的结构,图中有 N 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。

Dark 有 N–1 条主要边,并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外,Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态,你只能选择一条主要边切断。

一旦你切断了一条主要边,Dark 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道,一共有多少种方案可以击败 Dark。

注意,就算你第一步切断主要边之后就已经把 Dark 斩为两截,你也需要切断一条附加边才算击败了 Dark。

输入格式
第一行包含两个整数 N 和 M。

之后 N–1 行,每行包括两个整数 A 和 B,表示 A 和 B 之间有一条主要边。

之后 M 行以同样的格式给出附加边。

输出格式
输出一个整数表示答案。

数据范围

N≤100000,M≤200000,数据保证答案不超过231−1

输入样例

4 1
1 2
2 3
1 4
3 4

输出样例

3

题目描述

有一个由锁链组成的黑暗怪物(难道是启示录兽??),我们作为被选中的孩子,要变成拯救世界的英雄,击败他!

给一个无向图,图中有N个节点和两种类型的边,一种主要边一种附加边,主要边有N-1条,任意两点间都有一条主要边,附加边有M条。目标过切断边的连接,把无向图变成不连通的两部分。切断的规则是先切断一条主要边,再切断一条附加边。最后问我们有多少种方案可以达成目标

题目分析

我们把组成树的主要边称为“树边”,把附加边称为“非树边”。

那么,当如下图中,只有一条非树边的情况下,对于绿色边组成的环,当我们砍掉任意一条绿色树边的情况下,如果想让图不连通,就必须再砍掉一条非树边

(tips:下图中边的数字表示砍掉该树边之后,还需要再看几条非树边,才能使图不连通。)

如果再增加一条非树边,那么黄色树边组成的环,则也需要在砍掉一条树边之后,再砍掉一条非树边

通过上图,我们可以发现有两条边既在绿色边组成的环里,又在黄色边组成的环里,因此他们的数字为2

通过这种规律,我们就可以找到本题的基本思路:我们遍历每一条非树边,找到非树边形成的环,把环上的每一条树边的数字加一。

用上面的思路处理完之后,每条树边对应的数字就可以分成三类:

  1. 树边的数字是0,表示不需要再砍非树边就能达成目标,而根据题面给出的信息,必须砍一条非树边,那么此时,我们砍的这条非树边,就可以是任意一条,因此,这条树边能增加的方案就是m种,其中m为非树边的数量。

  2. 树边的数字是1,表示需要再砍一条非树边才能达成目标,那么这条树边所能增加的方案就是唯一一种。

  3. 树边的数字大于1,根据题面信息,但是你的能力只能再切断 Dark 的一条附加边,所以这种情况下,该树边无法提供方案。

综上,本题主要要处理的问题是,如何快速的给边的数字增加1,以及快速的求出每一个边的最终数字是多少

其实这个问题就是差分的使用场景

差分:将序列中某个区间[l,r]的所有数字加上指定的数。(差分不是本文重点,因此不过多描述)

基于差分的思路,我们可以扩展出树上差分

如果x和y之间连一条非树边,使他俩之间形成了环,那么我们就要给x到y这个环中的所有树边加上c(这里c==1)

做法是:

  1. d[x] += c;
  2. d[y] += c;
  3. p=LCA(x,y); d[p] -= 2c;

首先必须明确d数组的含义:d[i]表示点i到根节点的距离

我们知道d[x]x到根节点的距离,我们把d[x]+c,也就是把x到根节点的每一段都加上了c,同理,d[y]也是。那么,我们看图就可以看出来d[x]和d[y]实际上 都多加了一段黄色的部分,也就是他们的最近公共祖先到根节点的距离,因此,我们把这段减去两次,就表示x到y组成的环中,所有树边都加了c

Code

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;
int n, m;
int h[N], e[M], ne[M], idx; // 建图
// log10w 下取整是16 0~16是17个数
int depth[N], fa[N][17]; // LCA模板
int d[N]; // 存储边的数字
int q[N];
int res;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// LCA模板 初始化depth和fa 两个数组
void bfs() {
    memset(depth, 0x3fsizeof depth);
    depth[0] = 0, depth[1] = 1;
    int hh = 0, tt = 0;
    q[0] = 1;
    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q[ ++ tt] = j;
                fa[j][0] = t;
                for (int k = 1; k <= 16; k ++ )
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

// LCA模板
int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b]) 
            a = fa[a][k];
    if (a == b) return a;
    for (int k = 16; k >= 0; k -- ) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

// 返回每一棵子树边的数字的和
int dfs(int u, int father) {
    int ans = d[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != father) {
            int s = dfs(j, u);
            // 根据分析中的规则累加
            if (s == 0) res += m;
            else if (s == 1) res += 1;
            ans += s;
        }

    }
    return ans;
}

int main() {
    cin >> n >> m;
    memset(h, -1sizeof h);
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bfs();
    for (int i = 0; i < m; i ++ ) {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        d[a] ++ , d[b] ++ , d[p] -= 2;
    }
    dfs(1-1);
    printf("%d\n", res);
    return 0;
}

END

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1