树形结构3

Wangjunhao2011 · 2024-01-30 20:32:10 · 个人记录

树形结构3

重心

定义

定义：使得最大子树大小最小，那么这个点叫就被叫做树的重心。

这棵树的中心就是 1。

这棵树的中心就是 2。

这棵树的中心就是 1，2。

求解

朴素做法 O(N^2)

我们可以枚举出每个点为断点时，所产生的最大子树大小。某断点求当前最大子树大小的方法：对该点进行 dfs，找到以 i 为根节点的子树的大小记录到 sz_{i} 中，接着在该点的儿子中找 sz_{i} 最大的一个。

但是肯定有更优的解法。

一次 dfs，可以将每个节点 x 的子树分为两种：

1.根节点将要去的子树。（dfs 回溯时一定能获取类型 1 子树大小）

2.来时的子树，此时无法再递归回去。（假设断开来边，来时子树大小=总节点数-接下来获得的 sz_{i}，即等于 N- sz_{i} )

意味着一次 dfs 能够求出所有点作为重心能得到的最大子树大小 mss。我们取最小值即可，复杂度 O(n)。

重心的性质

性质1：重心点的最大子树大小不大于整棵树大小的一半

当边权为1时，树的重心存在以下性质:

设 mss(u) 表示以 u 为重心的最大子树，s_{0} (u)表示以u为根的子树大小，s_{u}(v) 表示以 u 为根的的子树 v 大小。

证明

设 u 为重心，v 为 u 的最大子树。

可以得出：S_{0}[u]-S_{u}[v]\ge S_{u}[v]\Longrightarrow S_{u}[v]\le \frac{S_{0}[u]}{2}

在整棵树中，存在 S_{0}[u]=n

所以 S_{u}[v]\le \frac{n}{2}得证

以某点为根，最大子树大小不超过 \frac{n}{2}的都是树的重心。

性质2：非空树有且仅有1-2个重心。当有两个重心时，树定有偶数个节点，且两个重心相邻

假设 u、v 为树上两个重心，u，v 分别为对方最长链上的点。

此时：

又设 k 为两个重心之间存在的点数。

由mss[u]=su[v]+k

推出 sv[u]=su[v]。

在 k 个点中选择中点 p，此时，