树分治

[Ir1d]

https://oi-wiki.org/graph/tree-divide/

[Cwolf9]

点分树build函数哪里，nd[tmp].fa不应该赋值为重心吗？为啥是now？

[KarlDe1]

3806洛谷RE?

[thallium]

@KarlDe1
3806洛谷RE?

我交了一个pr修复了，就是因为如果路径太大的话会数组越界

[shellspicker]

例题：点分治1
题目的说明里面，应该是边权而不是点权。

[cs142857]

我感觉这里的点分治的核心其实就是树的重心，如果了解了树的重心的做法其实就知道怎么做了，不如归类到“树的重心”那一篇？

[Singulet31258]

有个被外国人叫作 Centroid Decomposition 的算法，直译过来就是“重心分解”，思路跟点分治几乎一致。也有可能这个算法就是点分治，只是称呼不同而已。

[tiaotiao2011]

例题1参考代码的第68行是不是多余的？

[tiaotiao2011]

以及第82行

[EndlessCheng]

不需要计算两次 calcsiz。虽然说第二次 calcsiz 是为了算出重心的父节点连通块的大小，但实际上在求重心的时候，可以额外记录重心的父节点，这样后面遍历重心邻居时，可以特判邻居是父节点的情况，用 sum-sz[rt] 就可以算出父节点连通块的大小了。

[UnderTheTime]

对于点分治过程中计算 dis 时为什么单轮复杂度不会达到 $O(n^2)$ ？