未分类

DFS序列（$\mathrm{dfn}$）

在没有或存在一定限制条件的情况下，以DFS遍历经过的节点顺序构成的序列。记$\mathrm{dfn}(x)$为第一次访问该节点的时间戳，$\mathrm{seq}(t)$为访问序为$t$的节点。

容易发现，节点$x$的子树节点的$\mathrm{dfn}$一定是一段连续的区间。故我们可以使用数据结构方便地维护子树的信息。

（更多…）