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

最近公共祖先问题

最近公共祖先，又叫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, 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」