换根意义下的子树 DFS 序
stripe_python · · 个人记录
实际上,换根意义下的子树 DFS 序只有
- 若
r=x ,则x 子树 DFS 序为[1,n] 。 - 若
r \notin \text{subtree}(x) ,则x 子树 DFS 序仍为[\text{dfn}_x,\text{dfn}_x+\text{sz}_x) 。注意这里的\text{subtree}(r) 是在r_0 意义下定义的。 - 若
r \in \text{subtree}(x) ,找到x \to r 路径上的第一个节点y ,只要取y 子树的补集,则x 子树 DFS 序为[1,\text{dfn}_y) \cup [\text{dfn}_y+\text{sz}_y,n] 。下图给出了这种情况的一个例子。
在r_0 意义下有\text{dep}_y=\text{dep}_x+1 ,找到r 的\text{dep}_r-\text{dep}_x-1 级祖先即为y ,可以使用树上倍增优化。