思想
- 对于树结构，通常包括进入节点和离开节点的两次记录（即时间戳），形成一个长度为2N的序列（N为节点数）。
性质
-
子树连续性：同一子树的节点在DFS序中形成连续区间。例如，根节点的子树区间包含所有子节点的访问记录。
这个性质使得在子树上进行的修改、查询可以转换成区间修改、区间查询。dfs序的主要作用就是将一个子树变成序列上的一个连续区间。设in[x]为进入当前节点时的时间，out[x]为离开当前节点时的时间，那么子树x在dfs序里所对应的范围就是in[x]~out[x]。 -
括号化定理：若节点A的进入时间小于节点B的进入时间，且A的离开时间大于B的离开时间，则B是A的子节点。
-
线性化处理：DFS序将树结构转化为线性序列，便于使用线段树、树状数组等算法解决树上问题。
做法
-
子树操作：子树问题直接对应DFS序列上的一个连续区间。
-
路径操作：路径问题通常需要结合LCA，将路径拆解为u->lca和lca->v两部分处理。
工具
- LCA（最近公共祖先）：用于处理路径问题，常用倍增法或树链剖分求解。
- 树状数组/线段树：用于高效处理DFS序列上的区间修改与查询。
- 树上差分：巧妙地将路径修改转化为少量点的修改。
- 主席树（可持久化线段树）：用于处理树上路径的区间查询，例如查询路径上第k大的数。
拓展应用
- 虚树