首页 算法 图论

# 最近公共祖先问题

最近公共祖先，又叫 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 开始，向上走 2j2^j 步所到达的那个节点。

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

  1. fa[7, 0]=4 ：表示向上走 20=12^0=1 步，到达点 4;
  2. fa[7, 1]=2 ：表示向上走 21=22^1=2 步，到达点 2；
  3. fa[7, 2]=0 ：表示向上走 22=42^2=4 步，到达一个不存在的点；

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

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

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

    其实就是二次幂的计算形式，假如当前 j=2 ，则有 22=42^2=4；那么下一步就是 j=3 ，则有23=82^3=8；那么需要 8 通过232^3 来计算吗？显然是不需要的，因为我们可以把232^3 拆解成23=22+1=22∗22^3=2^{2+1}=2^2*2，这时候我们神奇的发现，在上一步我们已经把222^2 计算出来了，所以我们就把计算 232^3 转换成了两个 222^2 。

    用公式表示就是： 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, 0x3f, sizeof 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, -1, sizeof 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<int, int> 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, -1, sizeof 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, 0x3f, sizeof 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, -1, sizeof 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