DFS 序求 LCA

\(\verb!Update on 2025/8/20!\)：发现有几个地方写得有点问题，稍稍修整了下，同时也加了些东西。若发现问题一定要告诉我啊！
\(\verb!Update on 2025/9/09!\)：LCA 那章进行了一些修改。
\(\verb!Update on 2025/10/3!\)：自己写了个模版题，欢迎来提交：https://www.luogu.com.cn/problem/U622285。

会有一些小的修缮不会在这里提到。

众所周知，倍增、树剖、tarjan（离线）都能求 LCA，但是“时间戳 + ST 表”这个逆天组合也能求 LCA（至于为啥叫 DFS 序求 LCA 我不知道，跟大佬学的）。

比如说，这道题：https://www.luogu.com.cn/problem/U622285

强制在线，所以 \(\mathcal{O}(n)\) 的 tarjan 不可做；节点数较多，询问次数非常多，倍增一定过不去，即使是树剖也显得力不从心。

所以，来学习一个可以 \(\mathcal{O}(n\log n)\) 预处理、\(\mathcal{O}(1)\) 查询的新的求 LCA 的方法吧！

DFS 序

定义：在进行 DFS 时，每个节点在递归调用栈中的进出顺序的时间序列就是 DFS 序，时间戳（dfn）是指每个节点首次被访问的顺序编号。

举个例子：

其中字母代表每个节点的编号。

假设我们是按照这种顺序搜完整棵树的：
\(A\rightarrow B\rightarrow D\rightarrow E\rightarrow C\)

那么这棵树的 DFS 序就是：\(A,B,D,D,E,E,B,C,C,A\)。
每个节点对应的时间戳（dfn）见下表：

节点编号	时间戳（dfn）
\(A\)	\(1\)
\(B\)	\(2\)
\(C\)	\(5\)
\(D\)	\(3\)
\(E\)	\(4\)

求时间戳（dfn）的码儿：

int dfn[N],dfi;
void dfs(int u,int fa) {
    dfn[u]=++dfi;
    for (int i=h[u];i;i=ne[i]) {
        int v=e[i];
        if (v==fa) {continue;}
        dfs(v,u);
    }
}

求 DFS 序的码儿：

vector<int> res;
void dfs(int u,int fa) {
	res.push_back(u);
	for (int i=h[u];i;i=ne[i]) {
		int v=e[i];
		if (v==fa) {continue;}
		dfs(v,u);
	}
	res.push_back(u);
}

LCA

思路分析

对于同一棵树上的两个节点 \(x,y\)，假设它们的 LCA 为节点 \(z\)。

一个重要的性质：一个节点的祖先结点的时间戳一定小于这个节点的时间戳。

For example，若 \(a\) 是 \(b\) 的祖先，那么 \(dfn_a<dfn_b\)。

这个应该很好理解（毕竟要想访问一个节点必须先访问它的所有祖先节点）。

然后考虑怎么求 LCA。

先假设 \(dfn_x<dfn_y\)。（我想 \(dfn_x=dfn_y\) 的情况我就不用说了，特判掉就行了）

分类讨论一下：

\(x\) 不是 \(y\) 的祖先。
\(x\) 是 \(y\) 的祖先。

对于第一种情况

根据上面那条性质，可得出节点 \(z\) 的时间戳要小于其子树内的任意一节点（除了节点 \(z\)）的时间戳。

可以发现，时间戳在区间 \([dfn_x,dfn_y]\) 内的节点（蓝色 \(+\) 红色 \(+\) 节点 \(x,y\)。注意不包括节点 \(z\)，因为 \(dfn_z<dfn_x\)），有些节点的父亲节点是正是节点 \(z\)，并且一定存在这样的节点，就比如说节点 \(z\) 在 \(z-y\) 这一条链上的儿子节点 \(y^\prime\)（红色的那个节点）。

还有一点，时间戳在区间 \([dfn_x,dfn_y]\) 内的节点的父节点不可能在以节点 \(z\) 为根节点的子树以外，所以这些节点的父节点的时间戳最小只能是 \(dfn_z\)。

于是，暴力地去想的话，令 \(fa_u\) 表示 时间戳是 \(u\) 的节点 的父节点的时间戳，\(id_u\) 表示时间戳是 \(u\) 的节点的编号。那么节点 \(x\) 和节点 \(y\) 的 LCA 就是

\[id\left[\min\limits_{i=dfn_x}^{dfn_y}fa_i\right] \]

~~为了不让这个式子太过丑陋，最外面的那个 \(id\) 数组我用 C++ 语言写成了 \(id[.\ .\ .]\)，下同。~~

突然发现 \(fa_u\) 断不好句不太好理解。
这里再给出另一种说法：
令节点 \(p\) 的时间戳等于 \(u\)，那么 \(fa_u\) 表示的就是节点 \(p\) 的父节点的时间戳。

为了方便讲解，令 \(MIN(l,r)=\min\limits_{i=l}^rfa_i\)，那么节点 \(x\) 和节点 \(y\) 的 LCA 也可写作

\[id_{MIN(dfn_x,dfn_y)} \]

区间极值？还不带修？

看到这，你能想到什么？

ST 表！！！

不过先别急着激动，另一种情况还没讲。

对于第二种情况

其实这时 LCA 就是节点 \(x\)。

如果按照情况一的做法去做，那么显然是错的——节点 \(x\) 的父节点将会被错误地当成 LCA，但是节点 \(x\) 才是真正的 LCA。

那么，怎么处理呢？特判吗？

首先特判是不好判的，因为想判断所求的 LCA 是不是错误的并不是件易事。

但是呢，可以发现只有节点 \(x\) 的 \(fa_{dfn_x}\) 会导致 \(MIN(dfn_x,dfn_y)\) 过小，考虑将节点 \(x\) 扔掉。由于节点 \(x\) 一定有一个时间戳是 \(dfn_x+1\) 的子节点（\(fa_{dfn_x+1}=dfn_x\)），并且时间戳是 \(dfn_x+1\sim dfn_y\) 的节点的父节点一定还在以节点 \(x\) 为根的子树中，这确保了 \(MIN(dfn_x+1,dfn_y)\) 一定等于 \(dfn_x\)。

Q：为啥节点一定有一个时间戳是 \(dfn_x+1\) 的子节点？
A：因为访问到节点 \(x\) 后，第一个被访问的节点一定是节点 \(x\) 的子节点。

那么节点 \(x\) 和节点 \(y\) 的 LCA 为：

\[id\left[\min\limits_{i=dfn_x+1}^{dfn_y}fa_i\right] \]

即

\[id_{MIN(dfn_x+1,dfn_y)} \]

注意：下面框框里的内容针对于情况一。

但是这对情况一还适用吗？

答案是：仍然适用。

时间戳为 \(dfn_x+1\) 的节点一定还在以节点 \(z\) 为根节点的子树中。（毕竟那子树里还有一个节点 \(y\)）

并且节点 \(y^\prime\) 的时间戳一定是在 \([dfn_x+1,dfn_y]\) 这个范围之内的，因为 \(dfn_x<dfn_{y^\prime}\)，所以 \(dfn_x+1\le dfn_{y^\prime}\)。

因此这么搞还是适用于情况一的。

实现细节

设 ST 表数组是 \(st_{i,j}\)，且

\[st_{i,j}=id_{MIN(i,i+2^j-1)} \]

首先是初始化问题。

这个不难：

\[st_{i,0}=id_{fa_i} \]

利用 DFS 即可完成 ST 表的初始化：

int dfn[N],dfi;
void dfs(int u,int fa) {
	st[dfn[u]=++dfi][0]=fa;
	for (int i=h[u];i;i=ne[i]) {
		int v=e[i];
		if (v==fa) {continue;}
		dfs(v,u);
	}
}

接着是如何处理出 ST 表。

根据 \(st_{i,j}\) 的定义，可写出下列码儿：

#define Min(x,y) dfn[x]<dfn[y]?x:y

for (int i=2;i<=n;i++) {lg[i]=lg[i>>1]+1;}
for (int j=1;j<=lg[n];j++) {
	for (int i=1;i+(1<<j)-1<=n;i++) {
		st[i][j]=Min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
}

其中 \(n\) 表示节点数量，\(lg_i\) 表示的是 \(\lfloor\log_2 i\rfloor\)。

于是整个初始化正式完成！

如何查询呢？

除了我们上面花费大篇幅来讨论的两种情况，还要记得特判 \(x=y\) 的情况呀！

根据普通 ST 表的查询方式，可得码儿：

#define Min(x,y) dfn[x]<dfn[y]?x:y

int lca(int x,int y) {
	if (x==y) {return x;}  //记得特判哦！
	if ((x=dfn[x])>(y=dfn[y])) {swap(x,y);}
	//确保 dfn[x]<dfn[y]（此注释中的 x,y 是节点编号），因为我们是这样讨论的。
	int t=lg[y-x];  //y-(x-1)+1=y-x。
	return Min(st[x+1][t],st[y-(1<<t)+1][t]);
}

注：
你也可以令 \(st_{i,j}=MIN(i,i+2^j-1)\)，
按照思路分析那小章用 ST 表求出 \(MIN(dfn_x+1,dfn_y)\)，
最后再把时间戳转化为节点编号即可。

码儿

该讲的应该都讲完了，上码！

#include<bits/stdc++.h>
#define MIN(x,y) dfn[x]<dfn[y]?x:y
using namespace std;
const int N=5e5+5,M=N<<1;
int n,m,rt;
int st[N][20],lg[N],dfn[N],dfi;
int h[N],e[M],ne[M],idx=1;
inline int read() {
	int x=0,f=1;
	char c=getchar();
	while (!isdigit(c)) {f=(c=='-'?-1:1);c=getchar();}
	while (isdigit(c)) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
void add(int a,int b) {
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs(int u,int fa) {
	st[dfn[u]=++dfi][0]=fa;
	for (int i=h[u];i;i=ne[i]) {
		int v=e[i];
		if (v==fa) {continue;}
		dfs(v,u);
	}
}
int lca(int x,int y) {
	if (x==y) {return x;}
	if ((x=dfn[x])>(y=dfn[y])) {swap(x,y);}
	int t=lg[y-x];
	return MIN(st[x+1][t],st[y-(1<<t)+1][t]);
}
int main() {
	n=read();m=read();rt=read();
	for (int i=1;i<n;i++) {
		int a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	dfs(rt,0);
	for (int i=2;i<=n;i++) {lg[i]=lg[i>>1]+1;}
	for (int j=1;j<=lg[n];j++) {
		for (int i=1;i+(1<<j)-1<=n;i++) {
			st[i][j]=MIN(st[i][j-1],st[i+(1<<j-1)][j-1]);
		}
	}
	while (m--) {
		int x=read(),y=read();
		printf("%d\n",lca(x,y));
	}
	return 0;
}

此代码可通过洛谷上的 LCA 模板题。

经过修改可通过上面的那道题：https://www.luogu.com.cn/problem/U622285。

posted @ 2025-03-27 13:27 lyas145 阅读(406) 评论(5) 收藏举报

刷新页面返回顶部

lyas145 の Blogs

DFS 序求 LCA

DFS 序

LCA

思路分析

实现细节

码儿

公告