(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)$