专栏文章

DFS序与树链剖分

hhuge_wave
算法·理论参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minol981
此快照首次捕获于
2025/12/02 05:48
3 个月前
此快照最后确认于
2025/12/02 05:48
3 个月前
查看原文

前言

作者因DFS写得太糖，导致此题调试4h，一节课就过去了

DFS序

这是老师ppt中对DFS的讲解，但这讲了跟讲了一样

不包含树链的操作

我们对一棵树进行DFS，把刚搜到他的顺序计为 in[x]in[x] ，离开这个点时记为 out[x]out[x] 。很容的知道以 xx 为根的子树的 inin 值都在 [in[x],out[x]][in[x],out[x]] 之间，所以就可以把子树问题转为区间问题，可以用树状数组、线段树来快速处理
下面给出代码：
1点修改子树查
CPP
const int N=1e6+10;
int in[N],out[N],tr[N],cnt=0,a[N];
int maxn=1e6;
vector<int> g[N];
void xg(int x,int z){
	for(;x<=maxn;x+=x&-x){
		tr[x]+=z;
	}
}
int ask(int l,int r){
	int ans=0;
	for(;r>=1;r-=r&-r){
		ans+=tr[r];
	}
	l--;
	for(;l>=1;l-=l&-l){
		ans-=tr[l];
	}
	return ans;
}
void dfs(int x){
	cnt++;
	in[x]=cnt;
	for(int xx:g[x]){
		dfs(xx);
	}
	out[x]=cnt;
}
2

评论

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

正在加载评论...