专栏文章

冷门科技 —— DFS 序求解 LA

ssmall_lemon_qwq
算法·理论参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miniedqc
此快照首次捕获于
2025/12/02 02:55
3 个月前
此快照最后确认于
2025/12/02 02:55
3 个月前
查看原文
  • 该技巧目前已知的最早来源：我自己。
dfs 序求 k 级祖先无论是在实际效率，空间常数还是好写程度均吊打长链剖分。

定义

  1. dfs 序表示对一棵树进行深度优先搜索得到的结点序列。
  2. 设 did_i 为点 ii 的深度，其中根的深度为 11。

算法介绍

考虑现在我们要求节点 uu 的第 kk 级祖先，设答案为 ff，则 dfd_f 是已知的。
那我们现在在所有深度是 dfd_f 的点中找到 uu 的祖先即可。
显然，ff 是 uu 的祖先当且仅当以 ff 为根的子树包含以 uu 为根的子树。
于是可以转为 dfs 序。
设点 xx 的后代在 dfs 序上对应的区间为 [lx,rx][l_x,r_x]，那么查询就是问在深度为 dfd_f 对应的点对应的区间中，是 [lu,ru][l_u,r_u] 的超集的是哪个点，显然只会存在一个，二分秒了。
然后你发现可以将 lul_u 或 rur_u 丢掉，只保留一个，仍然可以做。
但是保留 rur_u 就可以直接用 lower_bound，所以我们选择保留 rur_u。
这是 P5903 【模板】树上 K 级祖先的代码。
875 字节，厉不厉害？
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,dep[500005],cnt,r[500005];
int nxt[500005],head[500005];
vector<pair<int,int>>vec[500005];
unsigned s;
void add(int u,int v){
	nxt[v]=head[u];
	head[u]=v;
}
inline unsigned get(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return s=x;
}
void dfs(int u){
	r[u]=++cnt;
	for(int v=head[u];v;v=nxt[v]){
		dep[v]=dep[u]+1;
		dfs(v);
		r[u]=r[v];
	}
	vec[dep[u]].push_back({r[u],u});
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q>>s;
	int rt=0;
	for(int i=1;i<=n;i++){
		int f(0);
		cin>>f;
		rt+=(!f)*i;
		if(f)add(f,i);
	}
	dep[rt]=1;
	dfs(rt);
	int lst=0,sum=0;
	for(int i=1;i<=q;i++){
		int u=(get(s)^lst)%n+1,k=(get(s)^lst)%dep[u];
		lst=lower_bound(vec[dep[u]-k].begin(),vec[dep[u]-k].end(),make_pair(r[u],-1ll))->second;
		sum^=1ll*i*lst;
	}
	cout<<sum;
	return 0;
}
当然，这份代码显然不是跑得很快的，这份才是：
SuccessCPP
#include<bits/stdc++.h>
using namespace std;
int n,q,dep[500005],cnt,r[500005];
vector<int>g[500005];
vector<pair<int,int>>vec[500005];
unsigned s;
inline unsigned get(unsigned x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return s=x;
}
void dfs(int u){
	r[u]=++cnt;
	for(int v:g[u]){
		dep[v]=dep[u]+1;
		dfs(v);
		r[u]=max(r[u],r[v]);
	}
	vec[dep[u]].push_back({r[u],u});
}
void read(auto&x){
	char c(getchar());
	while(c<'0')c=getchar();
	while(c>='0')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
signed main(){
	read(n),read(q),read(s);
	int rt=0;
	for(int i=1;i<=n;i++){
		int f(0);
		read(f);
		rt+=(!f)*i;
		g[f].push_back(i);
	}
	dep[rt]=1;
	dfs(rt);
	int lst=0;
	long long sum=0;
	for(int i=1;i<=q;i++){
		int u=(get(s)^lst)%n+1,k=(get(s)^lst)%dep[u];
		lst=lower_bound(vec[dep[u]-k].begin(),vec[dep[u]-k].end(),make_pair(r[u],-1))->second;
		sum^=1ll*i*lst;
	}
	cout<<sum;
	return 0;
}

和各种 LA 算法的对比

对比 DFS 序和重链剖分，预处理的时间常数减半（重链剖分需要两次 dfs），而且更好写，但两种算法表现都不错，因此树剖 LA 也是不错的选择。
对比 DFS 序和倍增，前者预处理复杂度更优，查询常数也更小。
对比 DFS 序和长链剖分，前者预处理复杂度更优，且实际效率也更高（访问连续性）。
对于其它算法，请读者自行比较。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...