DFS序

我们在处理一些树上计数问题时，经常由于数据量过大而树形结构的统计操作又十分复杂，所以常常需要将树形结构转换成更加便于查询和修改的线性结构，再结合树状数组或者线段树等高效的查询更新结构来解决问题，这时，为了将树形结构转换成线性结构，我们经常会用到的一个东西就是DFS序。

想要得到DFS序，只需要对树做一次DFS遍历，在遍历过程中记录每个点被遍历到的时间点，这里用一个\(，Orderin，Orderout\)时间戳数组来记录，以下面的树为例：

经过DFS后得到的DFS序为：

顶点序号 1 2 3 4 5 6 7
\(Orderin\) 4 1 5 2 7 6 3
\(Orderout\) 4 7 5 5 7 7 3

在\(Orderin,Orderout\)数组中\(序号Orderin[x] = 序号\)，所以用树状数组或者线段树维护时，只需要针对序号维护就可，如果要查询某个子树，只需要知道子树根节点\(x\)，然后查询序号\(Orderin[x] - Orderout[x]\)的区间值。