相当于静态的 LCT。

两张 OI Wiki 的图。

可以看出它整棵树并不是二叉树,每个重链组成一个 BST,并且其中序遍历的顺序就是原树按深度排序的顺序。

建树过程:

  1. 先剖分,得到重儿子、子树大小、轻子树大小。
  2. 提出每个重链,先遍历处理它的枝叶。
  3. 对于一个重链,找到它的重心做根,并把它尽量压扁以保证复杂度。

例题:

【模板】"动态 DP"&动态树分治

EOF

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

博客信息

作者
Jayun
时间
2023-11-02 08:32:27
博客类型