我们经常会遇到树的问题，但树是非线性的结构，操作起来始终还是麻烦，如果我们能把树改造成线性结构，有什么方法？对，就是今天要讲的DSF序；
dfs序呢，就是把一棵树区间化，我们用dfs的方式将它区间化。
如图：
其实就是用dfs全部遍历一遍，不过我们不能光遍历还有动些小手脚，我们要在遍历的同时记录每个节点进栈与出栈的时间序列。
介绍两个基本函数：in[x],out[x]
dfs从根节点开始，这俩函数就分别记录每个节点x进入与离开的时间戳
还有num[x]，表示第x个节点的编号
inline int dfs(int x,int fa,int time)
{
in[x]=++time;
num[time]=x;
for(int i=1;i<=e[x].size();i++)
{
int w=e[x][i];
if(w==fa)continue;//防止又从子节点找回去
dfs(w,x,time);
}
out[x]=time;
}
dfs(s,0,0);
（具体情况根据，根据题目来写）
你仔细观察会发现：
序根节点的进栈时间<子树的dfs<根节点的出栈时间
这样不就成一个区间了
in[x]~out[x]是x为根节点的子树，划分为一个区间
然后什么单点修改，区间查询，莫队都可以用在树上，而且dfs序也是树链剖分的前驱知识
光说可能不怎么懂，我去找一些题，做完再更新例题
京公网安备 11010502036488号