题目链接:P3379 【模板】最近公共祖先(LCA) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
LCA是什么?
LCA(Lowest Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。
求解LCA的方法
朴素法,复杂度O(N):先把两个点x和y跳到同一深度,然后同时往上跑,当x == y时返回x或y。当整棵树接近一条链状时,复杂度达到O(N)。
LCA倍增法,复杂度O(logN),这也是我们要写的方法。
首先要预处理出每个点的所有祖先。可以用二进制分解,logN来算出。
倍增法利用了二进制的性质,每一个非负整数都可以由二进制表示出来,那么我们fa[x][i]表示x向上跳了2 ^ i个格子之后所在的位置。
不难发现fa[x][0]就是x的父节点(向上走2^0格),而fa[x][i] = fa[fa[x][i - 1]][i - 1],也就是说x向上走2 ^ i格 = 向上走2 ^ (i - 1),再走2 ^ (i - 1),这里用到了动态规划的思想,因为在dfs递归到x时,x的父亲的fa是处理完了的。
处理完fa之后,我们就要求x和y的LCA了。
由朴素法提供的思路,我们先把x和y移动到同一深度。
设x的深度大于y(如果x深度小于y深度就交换x,y),从大到小(有点贪心的意思)遍历x的所有二进制位(假设为20位,基本够用),如果x向上移动后深度依然大于等于y就可以移动。最后一定能保证dep[x] == dep[y]。
举个例子,一开始dep[x] = 15, dep[y] = 2。x就向上走8 + 4 + 1步可以到y的深度。
当xy深度相同时,如果x==y就直接返回x或y。否则继续同时向上跑,如果x的2^i祖先和y的2^i祖先相等的话说明跑多了,如果不相等,说明还没到LCA,就可以往上跑,跑完之后可以保证x y一定位于LCA的下一层,那么LCA就是fa[x][0]或fa[y][0]。
完毕。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 5e5 + 10; int N, M, S, T = 20; int fa[maxn][25], dep[maxn]; vector<int> g[maxn]; void dfs(int x,int pre) { dep[x] = dep[pre] + 1; fa[x][0] = pre; for(int i = 1;i <= T; ++ i)fa[x][i] = fa[fa[x][i - 1]][i - 1]; for(auto &i : g[x]) { if(i == pre)continue; dfs(i, x); } } int LCA(int x,int y) { if(dep[x] < dep[y])swap(x, y); for(int i = T;i >= 0; -- i)if(dep[fa[x][i]] >= dep[y])x = fa[x][i]; if(x == y)return x; for(int i = T;i >= 0; -- i)if(fa[x][i] != fa[y][i])x = fa[x][i], y = fa[y][i]; return fa[x][0]; } signed main() { scanf("%lld %lld %lld", &N, &M, &S); for(int i = 1;i < N; ++ i) { int x, y;scanf("%lld %lld", &x, &y); g[x].push_back(y);g[y].push_back(x); } dep[0] = -1; dfs(S, 0);//构造树 while(M --) { int x, y;scanf("%lld %lld", &x, &y); printf("%lld\n", LCA(x, y)); } return 0; }
Comments 3 条评论
看了哥哥的文章,打比赛爆WA了 ( doge )
@嫩爹 好
@嫩爹 mua