最近公共祖先（LCA）

前言（需要图论和树的基础）

LCA中文名最近公共祖先（LCA）类型题目。求LCA是一个基本的树上问题，说的就是这么一个事:

首先给出一棵树，然后随意制定两个结点，需要你找到这两个结点各自的所有公共的祖先结点中深度最深的一个结点。

下面我会从最基本的思路->不断优化的基本思路来扩展解决这类问题的解题思路。

最近公共祖先（LCA）

原题

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

思路一：树的暴搜思路标记法（O(nm)）

思路：首先从x出发向根结点走，沿路标记所有的祖先结点，在x的祖先结点标记完成之后我们就可以从y出发向根结点走了，走到第1个被x标记的节点，就是LCA(x,y)。对于这道题目的Subtask #1全部都会TLE

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

using namespace std;
const int N = 5e5 + 10, M = 2 * N;
int n, m;
int e[M],ne[M],h[N],idx;
int depth[N], q[N], fa[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);
    int hh = 0, tt = 0;
    depth[0] = 0;
    depth[root] = 1;
    q[0] = root;
    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] = t;
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    while (depth[a] != depth[b]){
        a = fa[a];
    }
    if (a == b) return a;
    while (fa[a] != fa[b]) {
        a = fa[a];
        b = fa[b];
    }
    return fa[a];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int root;
    cin >> n >> m >> root;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    } 
    
    bfs(root);
    
    while(m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        cout << p << '\n';
    }
    return 0;
}

思路二：倍增法（O(nlog2n+mlog2n)）

思路：这里的倍增法实际上是一个递归或者说是一种DP的思维，非常得奇妙

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

using namespace std;
const int N = 5e5 + 10, M = 2 * N;
int n, m;
int e[M],ne[M],h[N],idx;
int depth[N], q[N], fa[N][22];

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);
    int hh = 0, tt = 0;
    depth[0] = 0;
    depth[root] = 1;
    q[0] = root;
    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 <= 21; 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 = 21; k >= 0; k--) {
        if (depth[fa[a][k]] >= depth[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 21; k >= 0; k--) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int root;
    cin >> n >> m >> root;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    } 
    
    bfs(root);
    
    while(m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        cout << p << '\n';
    }
    return 0;
}

思路三：Tarjan算法（其中最高效的一种思路，但是有一定的限制，O(n+m)）

持续更新中……

前言（需要图论和树的基础）

LCA中文名最近公共祖先（LCA）类型题目。求LCA是一个基本的树上问题，说的就是这么一个事:

首先给出一棵树，然后随意制定两个结点，需要你找到这两个结点各自的所有公共的祖先结点中深度最深的一个结点。

下面我会从最基本的思路->不断优化的基本思路来扩展解决这类问题的解题思路。

A:最近公共祖先（LCA）

原题

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $30%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

思路一：树的暴搜思路标记法（O(nm)）

思路：首先从x出发向根结点走，沿路标记所有的祖先结点，在x的祖先结点标记完成之后我们就可以从y出发向根结点走了，走到第1个被x标记的节点，就是LCA(x,y)。对于这道题目的Subtask #1全部都会TLE

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

using namespace std;
const int N = 5e5 + 10, M = 2 * N;
int n, m;
int e[M],ne[M],h[N],idx;
int depth[N], q[N], fa[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);
    int hh = 0, tt = 0;
    depth[0] = 0;
    depth[root] = 1;
    q[0] = root;
    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] = t;
            }
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    while (depth[a] != depth[b]){
        a = fa[a];
    }
    if (a == b) return a;
    while (fa[a] != fa[b]) {
        a = fa[a];
        b = fa[b];
    }
    return fa[a];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int root;
    cin >> n >> m >> root;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    } 
    
    bfs(root);
    
    while(m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        cout << p << '\n';
    }
    return 0;
}

思路二：倍增法（BFS版本，O(nlog2n+mlog2n)）

思路：这里的倍增法实际上是一个递归或者说是一种DP的思维，非常得奇妙

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

using namespace std;
const int N = 5e5 + 10, M = 2 * N;
int n, m;
int e[M],ne[M],h[N],idx;
int depth[N], q[N], fa[N][22];

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);
    int hh = 0, tt = 0;
    depth[0] = 0;
    depth[root] = 1;
    q[0] = root;
    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 <= 21; 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 = 21; k >= 0; k--) {
        if (depth[fa[a][k]] >= depth[b]) {
            a = fa[a][k];
        }
    }
    if (a == b) return a;
    for (int k = 21; k >= 0; k--) {
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int root;
    cin >> n >> m >> root;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    } 
    
    bfs(root);
    
    while(m--) {
        int a, b;
        cin >> a >> b;
        int p = lca(a, b);
        cout << p << '\n';
    }
    return 0;
}

思路三：Tarjan算法（其中最高效的一种思路，但是有一定的限制，O(n+m)）

持续更新中……

B：The Flee Plan of Groundhog

链接

题目描述

Groundhog was especially careful after the outbreak,so he put on his mask in the 1st bedroom early,and then walked on the way to the nth dormitory to play with Orange. There are n dormitories in ZLZX, which are connected by n−1 corridors. Each dormitory can be reached to each other.The length of each corridor is 1.The walking speed of Groundhog is 1 m/s.

At that moment the bad news came: After Groundhog set out for t{t}t seconds,Orange took his temperature, and it turned out to be 41℃ !!! In addition to grief and indignation, Orange decided to run to Groundhog, to tell him the news at the speed of 2 m/s.

Groundhog had to run, of course, but he was running too slow at 1 m/s . As he ran, he had an idea: if he ran with the best strategy, how soon would Orange catch up with him? Define that every second Groundhog moves and then Orange moves again. Groundhog can choose to stay put.
Groundhog would have solved that, of course, but he is running away now, so he give it to you, the smartest one.

输入描述:

1 2	`The first line contains two integers n,t。 The next n−1 lines，each line contains two integers x,y, indicating there is a corridor between the xth dormitory and the yth dormitory.`

输出描述:

1	`An integer, indicating the latest time for Orange to catch Groundhog.`

示例1

输入

复制

输出

复制

说明

After t seconds, Groundhog is in the 5th dormitory and Orange is in the 7th dormitory.At this point, the best way for Groundhog is to goto the 2nd dormitory or the 6th6^{th}6th dormitory.But wherever he goes, he will be immediately caught by Orange.

备注:

1	`1≤n≤105,1≤t≤n−1,1≤x,y≤n`

思路

首先分析一下題目：有一棵树，A在1，B在2，A的移动速度是1边/s，B的是2边/s（可以选择走1边），前 t s A 在不断走向B，B不动。前 t s A在不断走向B，B是不动的，之后B就要开始移动逃离 A 了，求A最晚被追到的时间。

一棵树的两个结点之间的路径的基本是唯一的。所以可以把 B 为根，用LCA的ST倍增板子求A最后到达的位置。随后我们就要开始逃离，考虑A,B到达每一个点的情况，考虑A到达每个点所需要的时间,对于这个点，取两个时间中的较小值，取 A 和 B第 1 次到这个点的时间。然后从 A 出发寻找最大的二者到达时间相等的点。

代码（LCA的DFS递增版本 + BFS）

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

using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, t;
vector<int> P[N];
int fa[N][21];
bool st[N];
int ans = 0;
int dist1[N], dist2[N];

void dfs(int root, int place) {
    fa[root][0] = place;
    for (int i = 1; i <= 20; i++) fa[root][i] = fa[fa[root][i - 1]][i - 1];
    for (auto &v : P[root]) {
        if (v != place) dfs(v, root);
    }
}

int LCA(int u, int k) {
    int bit = 0;
    while (k) {
        if (k & 1) u = fa[u][bit];
        k >>= 1;
        bit++;
    }
    return u;
}

// 被基本的东西搞死，需要非常注意这个st[k] = true; 是要写在for循环的外面的，否则肯定是不对的。
void bfs1(int kk,int dist[]) {
    memset(st, false, sizeof st);
    queue<PII> q;
    q.push({kk, 0});
    
    while (q.size()) {
        auto tt = q.front();
        q.pop();
        int k = tt.first, distance = tt.second;
        st[k] = true;
        for (int kkk: P[k]) {
            if (st[kkk]) continue;
            dist[kkk] = distance + 1;
            q.push({kkk, distance + 1});
        }
    }
}

void bfs2(int kk) {
    memset(st, false, sizeof st);
    queue<int> q;
    q.push(kk);
    while (q.size()) {
        int k = q.front();
        q.pop();
        st[k] = true;
        ans = max(ans, max((dist2[k] + 1) / 2, dist1[k]));
        if ((dist2[k] + 1) / 2 <= dist1[k]) continue;
        for (int kkk : P[k]) {                        
            if (st[kkk]) continue;            
            q.push(kkk);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> t;
    for (int i = 0; i < n - 1; i++) {
        int a, b; 
        cin >> a >> b;
        P[a].push_back(b);
        P[b].push_back(a);
    }
    // 1、下面利用LCA的DFS写法寻找到我们最终到达的结点位置
    dfs(n, 0);
    
    int kf = LCA(1, t);
    if (kf == 0) kf = n;
       
    // 2、下面我们通过BFS的方法分别求出 kf 和 n 到树上各节点位置的到达时间
    bfs1(kf, dist1);
    bfs1(n, dist2);
    bfs2(kf);
    
    cout << ans;
    return 0;
}

随笔——什么是MEX? 上一篇

杂题——How many answers are wrong 下一篇