树分块
树分块的方式
可以参考 真 - 树上莫队．
也可以参考 ouuan 的博客/莫队、带修莫队、树上莫队详解/树上莫队．
树上莫队同样可以参考以上两篇文章．
树分块的应用
树分块除了应用于莫队，还可以灵活地运用到某些树上问题中．但可以用树分块解决的题目往往都有更优秀的做法，所以相关的题目较少．
顺带提一句，「gty 的妹子树」的树分块做法可以被菊花图卡掉．
BZOJ4763 雪辉
先进行树分块，然后对每个块的关键点，预处理出它到祖先中每个关键点的路径上颜色的 bitset，以及每个关键点的最近关键点祖先，复杂度是 𝑂(𝑛√𝑛 +𝑛𝑐32)O(nn+nc32)
，其中 𝑛√𝑛nn 是暴力从每个关键点向上跳的复杂度，𝑛𝑐32nc32 是把 𝑂(𝑛)O(n) 个 bitset 存下来的复杂度．
回答询问的时候，先从路径的端点暴力跳到所在块的关键点，再从所在块的关键点一块一块地向上跳，直到 𝑙𝑐𝑎lca 所在块，然后再暴力跳到 𝑙𝑐𝑎lca．关键点之间的 bitset 已经预处理了，剩下的在暴力跳的过程中计算．单次询问复杂度是 𝑂(√𝑛 +𝑐32)O(n+c32)，其中 √𝑛n 是块内暴力跳以及块直接向上跳的复杂度，𝑂(𝑐32)O(c32) 是将预处理的结果与暴力跳的结果合并的复杂度．数颜色个数可以用 bitset 的 count()，求 mexmex 可以用 bitset 的 _Find_first()．
所以，总复杂度为 𝑂((𝑛 +𝑚)(√𝑛 +𝑐32))O((n+m)(n+c32))．
参考代码
---|---
### [BZOJ4812 由乃打扑克](https://hydro.ac/p/bzoj-P4812)
这题和上一题基本一样，唯一的区别是得到 `bitset` 后如何计算答案．
~~由于 BZOJ 是计算所有测试点总时限，不好卡，所以可以用`_Find_next()` 水过去．~~
正解是每 1616 位一起算，先预处理出 216216 种可能的情况高位连续 11 的个数、低位连续 11 的个数以及中间的贡献．只不过这样要手写 `bitset`，因为标准库的 `bitset` 不能取某 1616 位……
代码可以参考 [这篇博客](https://www.cnblogs.com/FallDream/p/bzoj4763.html)．
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/ds/tree-decompose.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/ds/tree-decompose.md "edit.link.title")
> __本页面贡献者：[Ir1d](https://github.com/Ir1d), [ouuan](https://github.com/ouuan), [StudyingFather](https://github.com/StudyingFather), [H-J-Granger](https://github.com/H-J-Granger), [CCXXXI](https://github.com/CCXXXI), [countercurrent-time](https://github.com/countercurrent-time), [Marcythm](https://github.com/Marcythm), [NachtgeistW](https://github.com/NachtgeistW), [Enter-tainer](https://github.com/Enter-tainer), [sshwy](https://github.com/sshwy), [Xeonacid](https://github.com/Xeonacid), [AngelKitty](https://github.com/AngelKitty), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [Suyun514](mailto:suyun514@qq.com), [weiyong1024](https://github.com/weiyong1024), [c-forrest](https://github.com/c-forrest), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [Henry-ZHR](https://github.com/Henry-ZHR), [HeRaNO](https://github.com/HeRaNO), [isdanni](https://github.com/isdanni), [kenlig](https://github.com/kenlig), [ksyx](https://github.com/ksyx), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Peanut-Tang](https://github.com/Peanut-Tang), [shuzhouliu](https://github.com/shuzhouliu), [SukkaW](https://github.com/SukkaW), [Tiphereth-A](https://github.com/Tiphereth-A)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用