树的重心

（2022.11.21 重写）

定义

设 $\newcommand\siz{\operatorname{siz}}\newcommand\hson{\operatorname{hson}}\siz(x)$ 表示 $x$ 的子树大小（含 $x$），$\hson(x)$ 表示 $x$ 的重儿子。将边 $(x,\hson(x))$ 称为一条重边，其余不满足该条件的边称为轻边；将相邻的重边两两相连形成的链称为重链。

命题

一棵以 $\newcommand\rt{\text{rt}}\rt$ 为根的树，其重心 $c$ 满足以下条件：

• $c$ 在以 $\rt$ 为顶的重链上；$(1)$
• $c$ 的所有祖先（记其中一个为 $x$），均满足 $\siz(\hson(x))>\frac{\siz(rt)}{2}$；$(2)$
• $\siz(\hson(c))\leq \frac{\siz(rt)}{2}$。$(3)$

（更多…）