标签: 重链

  • 求一棵树任意子树的重心

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

    (更多…)