DFS序求LCA

superl61 / 2024-09-25 / 原文

DFS序求LCA

介绍

欧拉序求LCA 的数组总是会忘记开两倍，并且预处理的常数较大。用 DFS序求LCA 可以解决这些问题。

欧拉序：进节点和出节点会重复记录节点。

DFS序：深度优先搜索的顺序，不会重新记录。

假设要求 $lca(u,v)$, 且 $dfn[u] < dfn[v]$。

那么 $dfn[u] \sim dfn[v]$ 的所有点都在 $lca(u,v)$ 子树中。

其中包括 $lca$ 在 $v$ 方向上的第一个点 $x$, 显然这个点是 $dfn[u] \sim dfn[v]$ 中 $dep$ 最小的，和欧拉序求LCA 一样，我们用 st表 找到这个位置就可以，min函数改为比较dep。

这样就找到了 $x$, 那么 $lca(u,v) = fa[x]$。

还有一种不用记录 $dep$ 仅依靠 $dfn$ 求解 lca 的小技巧：$dfn$ 改为记录每个点的父节点，最终 st表求出的值就是 lca。（详情见参考博客）

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

#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=(r);++i)
#define G(i,r,l) for(int i(r);i>=(l);--i)
#define int long long
using namespace std;
using ll = long long;
const int N = 5e5 + 5;
struct node{
	int v,ne;
}e[N << 1];
int n, m, s, idx = 0, cnt = 0;
int dfn[N], dep[N], fa[N], st[22][N], first[N];
void add(int x, int y){ e[++idx] = (node){y, first[x]}; first[x] = idx; }
int cmin(int x, int y){
	if(dep[x] < dep[y]) return x;
	return y;
}
void dfs(int u,int f){
	dfn[u] = ++cnt;
	st[0][cnt] = u;
	fa[u] = f;
	dep[u] = dep[f] + 1;
	for(int i = first[u]; i; i = e[i].ne){
		int v = e[i].v;
		if(v == f) continue;
		dfs(v, u);
	}
}
int lca(int u,int v){
	if(u == v) return u;
	if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
	int t = __lg(v - u++);
	return fa[cmin(st[t][u], st[t][v - (1 << t) + 1])];
}
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> s;
	F(i, 1, n-1){
		int u, v;
		cin >> u >> v;
		add(u, v),add(v, u);
	}
	dfs(s, 0); 
//	F(i, 1, n) cout << st[0][i] << ' '; cout << '\n';                 
	F(i, 1, 20) for(int j = 1; j + (1 << i) - 1 <= n ; ++j) 
		st[i][j] = cmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
	F(i, 1, m){
		int u, v;
		cin >> u >> v;
		cout << lca(u, v) << '\n';
	}
	return 0;
}