dfs序

定义

dfs序是对树进行dfs遍历得到的一个时间戳序列

dfs的模板

int tot,in[N],out[N];//in表示进入节点的时间戳，out表示出节点的时间戳，in可以表示区间的左边界l，out可以表示区间的右边界r
void dfs(int u){
    in[u]=++tot;  
    for(int i=0;i<t[x].size();i++){  
        int v=t[x][i];  
        dfs(v);  
    } 
    out[u]=tot;
}

树化成线段举例如下图

dfs序

应用

暂时没学到其他应用，先大体了解这个可以化树为线段的性质。

注意，节点化为线段之后的序号为in[u]。

不过既然可以化作线段，那么关于线段的操作都可以做，比如树状数组和线段树以及莫队。