- Update on 2023.7.17:该技巧目前已知的最早来源:skip2004。
- Update on 2023.7.17:比较时,取时间戳较小的结点也是正确的,不用记录深度。
DFS 序求 LCA 无论是从时间常数,空间常数还是好写程度方面均吊打欧拉序。
定义
DFS 序表示对一棵树进行深度优先搜索得到的 结点序列,而 时间戳 DFN 表示每个结点在 DFS 序中的位置。这两个概念需要着重区分。
算法介绍
考虑树上的两个结点
不妨设
当
根据性质,任何
考察
这意味着什么?我们只需要求在
这样做的正确性依赖于在 DFS 序
根据假设,此时
对于情况 1,
综上,若
预处理 ST 表的复杂度仍为
#include <bits/stdc++.h> using namespace std; constexpr int N = 5e5 + 5; int n, m, R, dn, dfn[N], mi[19][N]; vector<int> e[N]; int get(int x, int y) {return dfn[x] < dfn[y] ? x : y;} void dfs(int id, int f) { mi[0][dfn[id] = ++dn] = f; for(int it : e[id]) if(it != f) dfs(it, id); } int lca(int u, int v) { if(u == v) return u; if((u = dfn[u]) > (v = dfn[v])) swap(u, v); int d = __lg(v - u++); return get(mi[d][u], mi[d][v - (1 << d) + 1]); } int main() { scanf("%d %d %d", &n, &m, &R); for(int i = 2, u, v; i <= n; i++) { scanf("%d %d", &u, &v); e[u].push_back(v), e[v].push_back(u); } dfs(R, 0); for(int i = 1; i <= __lg(n); i++) for(int j = 1; j + (1 << i) - 1 <= n; j++) mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]); for(int i = 1, u, v; i <= m; i++) scanf("%d %d", &u, &v), printf("%d\n", lca(u, v)); return 0; }
和各种 LCA 算法的对比
对比 DFS 序和欧拉序,不仅预处理的时间常数砍半(欧拉序 LCA 的瓶颈恰好在于预处理,DFS 是线性),空间常数也砍半(核心优势),而且还更好写(对于一些题目就不需要再同时求欧拉序和 DFS 序了),也不需要担心忘记开两倍空间,可以说前者从各个方面吊打后者。
对比 DFS 序和倍增,前者单次查询复杂度更优。
对于 DFS 序和四毛子,前者更好写,且单次查询常数更小(其实差不多)。
对于 DFS 序和树剖,前者更好写,且单次查询复杂度更优(但树剖常数较小)。
将 DFS 序求 LCA 发扬光大,让欧拉序求 LCA 成为时代的眼泪!
标签:结点,int,mi,DFS,dfn,LCA From: https://www.cnblogs.com/wyb-blog/p/17964609