dfs序


dfs序是一种处理树的方法, 它可以把树上的操作变为序列操作, 从而简化树上的操作

如何生成dfs序

tree

首先, 设置一个全局变量dfs_clock, 它的作用是记录访问某个结点的时间

然后对树进行dfs, 每次访问到一个结点时dfs_clock都+1

然后根据dfs时访问的顺序将树的每一个结点的信息存储下来

比如上面那棵树的dfs序就是: 1,2,5,6,3,4,7,8,9

伪代码:

1
2
3
4
5
6
7
8
9
10
11
int dfs_clock(0);	//时间戳
int in[Mx],out[Mx]; //最先和最后访问时间
int a[Mx];
void dfs_order(int p)
{
a[++dfs_clock] = p;
in[p] = dfs_clock;
for(x=child of p)
dfs_order(x);
out[p] = dfs_clock;
}

作用

记录下最先和最后的访问时间其实是为了访问以某个结点为根的子树

原理就是在某个结点最先访问时间之后和最后访问时间之前, 它的子树已经遍历过了,
又因为每个结点都只会访问一遍, 所以在[in[p],out[p])之间的所有节点都是以p为根的子树上的结点

那么, 我们可以用树状数组/线段树存储dfs序, 这样就可以快速做树上差分了(O(logn)查询,O(logn)修改)
例题