关于树的重心的初步认识

本文从WordPress迁移而来, 查看全部WordPress迁移文章

由于cf的一道题了解了树的重心,发现对于处理数据结构和树DP可能很重要,是下一阶段的鼓捣对象

找了一篇博文初步看了一下,还没深入了解

http://fanhq666.blog.163.com/blog/static/81943426201172472943638/

  1. 重心的定义是:以这个点为根,那么所有的子树(不算整个树自身)的大小都不超过整个树大小的一半。
  2. 一些性质:
    1. 树中所有点到某个点的距离和中,到重心的距离和是最小的;如果有两个重心,那么他们的距离和一样。
    2. 把两个树通过一条边相连得到一个新的树,那么新的树的重心在连接原来两个树的重心的路径上。
    3. 把一个树添加或删除一个叶子,那么它的重心最多只移动一条边的距离。