毛毛虫剖分

概述

一种树的重标号方式。

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

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

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

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

  • 遍历非重儿子。

这样标号满足

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

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

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

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

例题

1.[NOI2021] 轻重边

2.「GLR-R3」谷雨

只需要维护毛毛虫的信息,所以可以对毛毛虫顺序标号。

参考

毛毛虫剖分