最近接触到一些 DFS 序的题，它可以用来解决一些关于子树的问题。

  DFS 序本质就是一棵树在深度优先搜索时访问节点的顺序。比如有下面一棵树，其 DFS 序就是 $1 \; 2 \; 4 \; 7 \; 8 \; 5 \; 3 \; 6 \; 9$。

  DFS 序有一个很重要的性质，以节点 $u$ 为根的子树中所有的节点在 DFS 序中是连续的一段，并以 $u$ 开头。比如上图中，以 $2$ 为根的子树就有 $1 \; [{\color{red}{2}} \; {\color{red}{4}} \; {\color{red}{7}} \; {\color{red}{8}} \; {\color{red}{5}}] \; 3 \; 6 \; 9$。以 $6$ 为根的子树就有 $1 \; 2 \; 4 \; 7 \; 8 \; 5 \; 3 \; [{\color{red}{6}} \; {\color{red}{9}}]$。以 $5$ 为根的子树就有 $1 \; 2 \; 4 \; 7 \; 8 \; [{\color{red}{5}}] \; 3 \; 6 \; 9$，以此类推。

  如何求得以 $u$ 为根的棵子树在 DFS 序中对应的连续一段序列的左端点和右端点呢？定义 $\text{tin}_u$ 表示第一次访问到节点 $u$ 的时间，对应序列的左端点。定义 $\text{out}_u$ 表示访问完以 $u$ 为根的子树的时间，对应序列的右端点。可以通过以下代码求出每个节点的 $\text{tin}$ 和 $\text{tout}$。

void dfs(int u, int pre) {
    tin[u] = ++sz;
    for (int i = head[u]; i != -1; i = ne[i]) {
        if (e[i] != pre) {
            dfs(e[i], u);
        }
    }
    tout[u] = sz;
}

  上图中每个节点的 $\text{tin}$ 和 $\text{tout}$ 就是：

  DFS 序可以将树形结构转换成序列的形式，这使得在子树上进行的修改和查询操作可以转换为区间修改和区间查询，而区间的操作可以结合线段树或树状数组来优化。比如如果修改操作为给某个子树中的节点都加上一个值，查询操作为求某个节点的值。那么就可以求出 DFS 序，然后用树状数组维护一个差分数组，就变成了区间修改，单点查询。当给以 $u$ 为根的子树中的节点都加上 $c$，那么在差分数组中有 $d_{\text{tin}_u} \gets d_{\text{tin}_u} + c$，$d_{\text{tout}_u + 1} \gets d_{\text{tout}_u + 1} - c$。查询某个节点的值则对差分数组求前缀和即可。

  其他更多关于 DFS 序的应用可以参考博文。

参考资料

  DFS 序入门：https://www.luogu.com.cn/blog/p6174/dfs-xu-ru-men

  dfs序和欧拉序：https://www.cnblogs.com/stxy-ferryman/p/7741970.html