DFS序学习
对于一棵树,将他DFS展开成一个数组,就是DFS序,它的作用有很多,下面再说;
先放代码:
dfs序板子:
void dfs(int x,int pre,int d)//L,R表示一个子树的范围
{ //当前节点,父节点,深度
L[x]=++tot;//当前节点的左时间
dep[x]=d;//记录深度
for(int i=0;i<e[x].size;++i)//遍历子节点
{
int y=e[x][i];// 子节点
if(y==pre)// 防止回溯
continue;
dfs(y,x,d+1);//继续dfs,深度++;
}
R[x]=tot;//该子树结束遍历
}
它是将一棵树,按照DFS遍历顺序将他展开成一个数组,展开后的数组中,每个下标对应的元素就是节点元素;
每个节点元素有两个属性,L和R,表示的是从L开始进入x节点,直到最后R是该x的子树遍历完成,因此对应线段树的修改x的子树的时候,直接修改L(x)~R(x)的区间范围即可;
好了,开始介绍DFS序:
dfs序:就是从一棵树的根节点出发,dfs遍历时依次经过的节点序列 ;
dfs序可以有很多种
dfs遍历,经历当前节点的所有子节点,后回溯到当前节点,
遍历之前,任何子节点都没有被访问过
遍历后,所有子节点必定都被访问过了,
然后离开当前子树,回到父节点,在访问其他子树,同一子树的节点在bfs序中一定是连续的;
实现:
设置一个时间time=0,每遍历到一个新的节点就+1,当前节点的访问时间范围即当前节点的访问标号范围
设in[x]为进入节点的时间,out[x]为离开当前节点的时间,子树在dfs序中对应的范围就是in[x]~out[x];
他的DFS序就是0 1 2 3 4 5(不唯一,也可以是:0 3 4 5 1 2什么的,对结果一般无影响)
看一些大佬的博客对DFS序的一些变形和应用,总结出7点,便于以后实现
常用搭配:dfs序+线段树 ;
dfs序问题:
1.对于某个节点 x 权值加上一个数 W ,查询某个子树 x 里所有点权的和;
2.对节点 x 到 y 的最短路上所有点都加上一个数 W 查询某个点的权值;
等价于:
x到根节点路径上所有点权加W;
y到根节点路径上所有点权加W;
对LCA(x,y)到根节点路径上所有点权值减W;
对LCA(x,y)的父节点 fa(LCA(x,y))到根节点路径上所有权值减W;
3. 对节点 x 到 y 的最短路上所有点权都加一个数W,查询某个点子树的权值之和
修改节点A,查询节点B时;
只要A在B子树内,Y值就会增加:W*(dep[A]-dep[B]+1)
=>W*(dep[A]+1)-W*dep[B];
处理两个数组:
sum1 更新 W*(dep[A]+1), sum2 更新 W;
每次查询结果为sum1(R[B])-sum1(L[B]-1)-(sum2(R[B])-sum2(L[B]-1))*dep[B];
4.对某个点 X 权值加上一个数 W ,查询 X 到 Y 路径上所有点权之和.
问题转化:
x 到根节点的和 + y 到根节点的和 - lca(x,y)到根节点的和 - fa(lca(x,y))到根节点的和;
更新x权值时,只会对他的子树产生影响,对 x 的子树的每个节点到跟的距离都加了 W ;
用"刷漆"(差分前缀和),更新一个子树的权值,
给L[x]加上W,给R[x]+1减去W,那么sum(1~L[k])就是k到根节点的路径点权和;
5.对节点 x 的子树所有节点加上一个值 W ,查询 x 到 y 的路径上所有点的权值和
同(4):
x 到根节点的和 + y 到根节点的和 - lca(x,y)到根节点的和 - fa(lca(x,y))到根节点的和;
同(3): B在A的子树内,A对B有贡献;W*(dep[B]-dep[A]+1)
=>W*(1-dep[A])+W*dep[B];
两个数组sum1 记录W*(dep[A]+1), sum2 记录 W ;
答案就是 sum2*dep[B]-sum1 ;
6.对子树x中所有节点加上一个值W,查询某个点的值;
对DFS序来说,子树内所有节点加 W ,就是一段区间加 W;
区间修改,单点查询:方法有 (a): 树状数组+刷漆 ,(b): 线段树
7.对子树 x 里的所有节点加上一个值 W ,查询某个子树的权值的和:
子树所有节点加 W ,就是区间加 W ,查询某个子树的权值和,就是查询某段区间的和;
区间修改+区间求和,线段树