树的重心

(2022.11.21 重写)

定义

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

命题

一棵以 rt\newcommand\rt{\text{rt}}\rt 为根的树,其重心 cc 满足以下条件:

  • cc 在以 rt\rt 为顶的重链上;(1)(1)
  • cc 的所有祖先(记其中一个为 xx),均满足 siz(hson(x))>siz(rt)2\siz(\hson(x))>\frac{\siz(rt)}{2}(2)(2)
  • siz(hson(c))siz(rt)2\siz(\hson(c))\leq \frac{\siz(rt)}{2}(3)(3)

(更多…)

More
  • 2021年7月23日