【图论】树的重心

更新于 分类于 ， 阅读次数： 本文字数： 677 阅读时长 ≈ 1 分钟

补档树的重心

定义

对于无根树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心

特性

  • 树的重心至少一个最多两个，如果是两个它俩相邻。
  • 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
  • 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
  • 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int sz[N], weight[N], centroid[2];
//sz[i]是i节点（包括自己）的节点个数（带权），weight[i]是最大子树的大小
int cnt = 0; // centroid[0...cnt]为所有重心
void dfs(int rt, int from)
{
    sz[rt] = w[rt]; //节点权值，如果不带权就是1
    weight[rt] = 0; //
    for (auto v : tree[rt])
    {
        if (v == from)
            continue;
        dfs(v, rt);
        sz[rt] += sz[v];
        weight[rt] = max(weight[rt], sz[v]);
    }
    weight[rt] = max(weight[rt], tot - sz[rt]);
    // dfs更新过了此时有根树的子树大小，还需要用上面的部分来更新
    if (weight[rt] <= (tot >> 1))
        centroid[cnt++] = rt;
}