青岛的网站设计公司,邳州做网站的公司,广州哪里能买到正品港版黄道益活络油,快速网站开发 带数据库【模板】最近公共祖先#xff08;LCA#xff09;
https://www.luogu.com.cn/problem/P3379
题目描述
如题#xff0c;给定一棵有根多叉树#xff0c;请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N , M , S N,M,S N,M,S#xff0c;分别表示…【模板】最近公共祖先LCA
https://www.luogu.com.cn/problem/P3379
题目描述
如题给定一棵有根多叉树请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N , M , S N,M,S N,M,S分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N − 1 N-1 N−1 行每行包含两个正整数 x , y x, y x,y表示 x x x 结点和 y y y 结点之间有一条直接连接的边数据保证可以构成树。
接下来 M M M 行每行包含两个正整数 a , b a, b a,b表示询问 a a a 结点和 b b b 结点的最近公共祖先。
输出格式
输出包含 M M 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 % 30\% 30% 的数据 N ≤ 10 N\leq 10 N≤10 M ≤ 10 M\leq 10 M≤10。
对于 70 % 70\% 70% 的数据 N ≤ 10000 N\leq 10000 N≤10000 M ≤ 10000 M\leq 10000 M≤10000。
对于 100 % 100\% 100% 的数据 1 ≤ N , M ≤ 500000 1 \leq N,M\leq 500000 1≤N,M≤500000 1 ≤ x , y , a , b ≤ N 1 \leq x, y,a ,b \leq N 1≤x,y,a,b≤N不保证 a ≠ b a \neq b ab。
样例说明
该树结构如下 第一次询问 2 , 4 2, 4 2,4 的最近公共祖先故为 4 4 4。
第二次询问 3 , 2 3, 2 3,2 的最近公共祖先故为 4 4 4。
第三次询问 3 , 5 3, 5 3,5 的最近公共祖先故为 1 1 1。
第四次询问 1 , 2 1, 2 1,2 的最近公共祖先故为 4 4 4。
第五次询问 4 , 5 4, 5 4,5 的最近公共祖先故为 4 4 4。
故输出依次为 4 , 4 , 1 , 4 , 4 4, 4, 1, 4, 4 4,4,1,4,4。
2021/10/4 数据更新 fstqwq应要求加了两组数据卡掉了暴力跳。
代码
倍增算法
#include bits/stdc.h
#define endl \n
using namespace std;
vectorvectorint e; // 存储每个节点连接的边
vectorvectorint fa; // 存储节点的跳跃情况
vectorint 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;
vectorbool vis; // 用来存储是否已经访问
vectorvectorint e; // 存储每个节点连接的边
vectorint fa; // 存储节点的父节点
vectorvectorpairint, int query; // 存储要查询的
vectorint 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]);
}
