一种基于dfn求LCA的方法
2025-10-30 23:28:31
发布于：广东
9阅读
0回复
0点赞
参考文章：https://www.luogu.com.cn/article/pu52m9ue
rt，可以看出常数远远小于欧拉序求 LCA，并且拉爆朴素倍增写法。
做法也不难，懒得讲了。（其实我也只是听说可以对两个点 dfn 之间的所有点进行 RMQ，然后自己推出来做法的）
#include <iostream>
#include <cstdio>
#include <vector>
#define rank CSP_S_rp_plus_plus
#define log2 LCA_is_cool
using namespace std;
vector <int> v[500005];
int father[500005];
int log2[500005];
int dep[500005];
int curdfn;
int dfn[500005], rank[500005];
int st[500005][20];
int n, m, k;
int min_dep(int x, int y){
return (dep[rank[x]] < dep[rank[y]] ? x : y);
}
void dfs(int cur, int fa){
dfn[cur] = (++curdfn);
rank[curdfn] = cur;
father[cur] = fa;
dep[cur] = dep[fa] + 1;
for(int i:v[cur]){
if(i == fa) continue;
dfs(i, cur);
}
}
int lca(int x, int y){
if(x == y) return x;
int l = dfn[x], r = dfn[y];
if(l > r) swap(l, r);
l++;
int k = log2[r - l + 1];
return father[rank[min_dep(st[l][k], st[r - (1 << k) + 1][k])]];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for(int i = 2; i <= n; i++){
log2[i] = log2[i >> 1] + 1;
}
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(k, k);
for(int i = 1; i <= n; i++){
st[i][0] = i;
}
for(int i = 1; i < 20; i++){
for(int j = 1; j <= n; j++){
if(j + (1 << i) - 1 > n) continue;
st[j][i] = min_dep(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
}
}
while(m--){
int x, y;
cin >> x >> y;
cout << lca(x, y) << '\n';
}
return 0;
}
时间复杂度：。
有帮助，赞一个