DFS序求LCA

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;
}

参考博客

冷门科技 —— DFS 序求 LCA - By Alex_Wei