树的算法: 寻找树的重心

Posted on Edited on In , Word count in article: 769 Reading time ≈ 3 mins.

概述

  • 针对于无根树(所有结点均可作为根结点且对答案没有影响)，以树的重心为根结点能在分治思想中减少递归层次 其定义为：删除树的重心后，剩下的若干个连通分支各自的结点数不超过总结点数的一半 为表述方便，下称树的结点数→树的大小、向上/向下表示以一个确定的结点为根结点的情况下形成的有向树的方向、一个结点的子树→以该结点为根结点的有向树中，该结点的子树
  • 树的重心的性质有：
    • 树的重心有1 ∼ 2个，若有两个重心则它们相邻
    • 在无权树中，所有点到某点的距离和中，到树的重心的距离和是最小的(若有两个重心则到它们的距离和相等)
    • 合并两棵无根树，则新树的重心在两棵旧树重心之间的路径上 直接连接两个原有重心(而不是其它结点)能够最快速度找到新树的重心(两个原有重心之一、或两个都是)
    • 若上述两棵无根树中的一棵为平凡树，则新树重心不仅在旧树重心和该平凡树之间的路径上，而且离旧树重心最多一条边

算法结构

  • 考虑以任意结点为根结点(转化为有根树)，要求树中某个分支结点的子树大小，其向下子树大小只需要深搜即可 而其向上子树(只有一个、不包括该结点)大小为总结点数减去其向下子树(包括该结点)大小 因此对于所有结点，均可用这种方法求出其子树大小，然后根据定义(记录子树的最大值)求重心(所有结点子树大小最大值中最小的那个不超过总结点数的一半)即可

  • 时间复杂度O(n)

    ```c++ // 随意选择初始结点作为根结点, 这里选择结点1 // 采用链式前向星存树(且为了方便、边的next为0时表示空) int i, size[VN], w[VN], g[2]; // 分别表示 向下子树大小、所有子树大小的最大值、重心编号 void getCenter(int pos, int fa) { // 表示当前遍历的结点、当前结点的爹 // 该函数只会访问每个结点一次, 初始时设置当前结点的大小为1(后续更新), 表示包括其本身 size[pos] = 1; w[pos] = 0; // 当前没有计算出任何子树的大小, 最大值自然为0 for (i = head[pos]; i; i = edge[i].next) { if (edge[i].to != fa) { // 不计算向上子树 getCenter(edge[i].to, pos); // 深搜计算出size[edge[i].to] size[pos] += size[edge[i].to]; w[pos] = max(w[pos], size[edge[i].to]); // 向下子树的最大值 } } w[pos] = max(w[pos], VN - size[pos]); // 再和向上子树大小比 if (w[pos] <= (VN >> 1)) { g[g[0] != 0] = pos; // 记录该重心 } }