树上问题3——树的重心

概念

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

假定一个根，DFS 处理出每棵子树的大小，那么删掉点 $x$ 之后，剩下的连通块中，有它的所有子树，以及它的“上方子树”（即它父亲出发的那些点），因此大小为max(size(y),n-size(x),y∈son[x])。

对每个结点将上面的式子计算出来，取最小值所在的结点即为重心。

性质

树的重心如果不唯一，则至多有两个，且这两个重心相邻。

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

如果树的重心有两个，那么去掉连接这两个重心的边，剩下的两棵子树大小一样。

把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

例题

1. CF685B

题面

给定一棵有 $n$ 个结点有根树和 $k$ 个询问，每个询问是问一棵子树（有根树意义下且包含整颗树本身）的重心是哪一个节点。

输入：第一行两个整数 $n,k$，第二行 $n-1$ 个整数，第 $i$ 个数是 $i+1$ 号结点的父结点编号，接下来 $k$ 行每行一个整数表示要询问子树的根结点编号。

输出：$k$ 行，每行一个整数表示询问的答案。

数据范围：$n≤3 \times 10^5$。

解析

肯定不能分别对每棵子树都求一次，$O(n^2)$ 会超时。

根据之前的第四条性质，对于一棵以点 $u$ 为根的子树，其重心一定在所有以 $u$ 的直接子节点为根的子树的重心到点 $u$ 的路径上。

类似于上文提到的 DFS 求重心方法，对于每棵以节点 $u$ 为根的子树，先求出所有以其直接子节点为根的子树的重心（叶子节点的重心是其本身），然后向上判断路径上的节点是不是重心即可。

时间复杂度为 $O(n)$ 可以求出所有子树的重心。

2. CF1406C

题面

给定一棵节点数为 $n$ 的树， 删一条边然后加上一条边， 使得该树的重心唯一。删掉的边和加上的边可以是同一条。多组数据。

输入：第一行数据组数 $t$，每组数据第一行两个整数 $n,k$，接下来 $n-1$ 行每行两个整数表示一条边。

输出：每组测试数据输出 $2$ 行，第一行两个整数表示删除的边的端点，第二行两个整数表示增加的边的端点。

数据范围：$t≤10^4,3≤n,\sum n≤10^5$。

解析

注意到之前的第一条性质，树要么只有一个重心，要么有两个相邻的重心。

如果只有一个重心，则随便删一条边再加一条边即可。

所以重点是两个相邻的重心。

那么有一个性质：把这两个重心相连的边删除之后，树的两部分大小相等。

这个反证法即可。

因此我们直接把一棵子树中的一个叶子移动到另一棵子树上即可。

作业

2. P1364 P1395 P5536 P3304 P1099