ChungZH 的小窝
·
点分治笔记
📝
内容提要
点分治，外国人称之为 Centroid decomposition，重心分解。 何为树的重心 学习重心分解之前，自然要先了解重心。 下面统一用 $n$ 表示树上结点的个数。 在一棵树中，如果删除一个顶点后得到的最大子树的顶点数最少，那么这个点就是树的重心（Centroid）。 重心的性质： 删除重心后得到的所有子树，其顶点数必然不超过...
➡️
