P3379 【模板】最近公共祖先（LCA）

【模板】最近公共祖先（LCA）

https://www.luogu.com.cn/problem/P3379

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

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

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

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

样例说明：

该树结构如下：

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

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

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

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

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

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

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。

代码

倍增算法

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
vector<vector<int>> e;   // 存储每个节点连接的边
vector<vector<int>> fa;  // 存储节点的跳跃情况
vector<int> dep;         // 存储节点的深度void dfs(int x, int y) {dep[x]   = dep[y] + 1;  // 深度加1fa[x][0] = y;           // 确认父节点// 从前往后推出父节点for (int i = 1; i <= 18; i++) {fa[x][i] = fa[fa[x][i - 1]][i - 1];}// 递归遍历for (auto i : e[x]) {// 如果不是父节点，那么就dfsif (i != y) dfs(i, x);}
}int lca(int u, int v) {// 首先保证u深度更大if (dep[u] < dep[v]) swap(u, v);// 将u和v深度对齐for (int i = 18; ~i; i--) {// 一直往上跳，不断接近vif (dep[fa[u][i]] >= dep[v]) {u = fa[u][i];}}// 如果u和v相等，那么直接返回vif (u == v) return v;// 否则一起向上寻找lcafor (int i = 18; ~i; i--) {if (fa[u][i] != fa[v][i]) {u = fa[u][i];v = fa[v][i];}}// 因为一定会到lca的下一层，所以直接返回最后的父节点return fa[u][0];
}void solve() {// N为树的节点个数，M为询问个数，S为根节点序号int N, M, S;cin >> N >> M >> S;e.resize(N + 1);fa.resize(N + 1);for (int i = 0; i <= N; i++) {// N最大为500000，所以深度最高为2的18次方，19就会越界fa[i].resize(19);}dep.resize(N + 1, 0);  // 初始化深度为0// 输入N-1个边for (int i = 1; i <= N - 1; i++) {int a, b;cin >> a >> b;// 最开始无向，所以两个都要插入e[a].push_back(b);e[b].push_back(a);}dfs(S, 0);// 输入M个查询for (int i = 1; i <= M; i++) {int u, v;cin >> u >> v;// 寻找lcacout << lca(u, v) << endl;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}

tarjan算法

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
vector<bool> vis;                      // 用来存储是否已经访问
vector<vector<int>> e;                 // 存储每个节点连接的边
vector<int> fa;                        // 存储节点的父节点
vector<vector<pair<int, int>>> query;  // 存储要查询的
vector<int> ans;                       // 存储结果
// 并查集——路径压缩
int find(int u) {if (u == fa[u]) return u;return fa[u] = find(fa[u]);
}void tarjan(int u) {// 首先标记已经访问vis[u] = true;// 访问该节点的所有子节点for (int v : e[u]) {// 不能访问已经访问过的节点if (!vis[v]) {// 递归tarjantarjan(v);// 明确父节点fa[v] = u;}}// 在离开时查询for (auto q : query[u]) {int v = q.first;int i = q.second;// 如果该节点的另一半也访问过了，那么说明现在可以找到共同祖先if (vis[v]) {ans[i] = find(v);}}
}void solve() {// N为树的节点个数，M为询问个数，S为根节点序号int N, M, S;cin >> N >> M >> S;fa.resize(N + 1);vis.resize(N + 1);e.resize(N + 1);query.resize(M + 1);ans.resize(M + 1);// 初始化每个节点的父节点为自己iota(fa.begin(), fa.end(), 0);// 输入N-1个边for (int i = 1; i <= N - 1; i++) {int a, b;cin >> a >> b;// 最开始无向，所以两个都要插入e[a].push_back(b);e[b].push_back(a);}// 输入M个查询for (int i = 1; i <= M; i++) {int u, v;cin >> u >> v;// tarjan为离线算法，所以要先存储查询query[u].push_back({ v, i });query[v].push_back({ u, i });}// tarjantarjan(S);// 输出存储的结果for (int i = 1; i <= M; i++) {cout << ans[i] << endl;}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;
}

• 并查集的路径压缩：路径压缩的基本思想是，在执行查找操作时，将访问路径上的所有节点直接连接到根节点上。这样做的目的是在下一次查找操作时，能直接访问到根节点，从而减少路径长度，提高查找效率。

  // 并查集——路径压缩
  int find(int u) {if (u == fa[u]) return u;return fa[u] = find(fa[u]);
  }