毛毛虫剖分

notes

概述

一种树的重标号方式。

先对树进行重剖。对树进行 dfs，当遍历到 $u$ 时

  • 若 $u$ 未被标号，对 $u$ 进行标号。

  • 若 $u$ 为重链的的链头，遍历这条重链，对相邻非重链上的节点依次标号

  • 若 $u$ 有重儿子，遍历重儿子。

  • 遍历非重儿子。

这样标号满足

  • 一条重链除链头外标号连续。

  • 一条重链的邻点标号连续。

  • 子树标号为两段不相交的连续区间。

那么链、子树、链的邻点的信息都可以维护了。

例题

参考