Tree Centroid

无根树中的「子树」通常指它的一个连通子图．在讨论重心时，部分作者会用「子树」一词特指不包含某结点的极大连通子图，或者特指将某条边删去后得到的两个连通分量之一．容易验证，这两种方式定义得到的「子树」集合是一致的，且不包括整棵树自身．由于它和有根树的子树集合并不一致，本文将避免对无根树使用「子树」概念．

在实际求解重心或处理某些问题时，通常存在一个默认的树根．此时，将非根结点 $v$ 删掉得到的连通分量中，除了该结点的子结点对应子树外，还有一棵「向上」的子树．此时，设结点 $v$ 的父结点为 $u$，这棵「向上」的子树就是 $T_u^{(v)}$．本文在提及这类子图时，会显式地称呼它为「向上」的子树．若无特殊说明，本文提及的子树均不包括这类「向上」的子树．

=== "无根树版本"
    1.  在树中删去结点 $v$ 后，得到的图 $T\setminus\{v\}$ 中每个连通分量的大小均不超过原树结点数的一半．
    2.  在所有删去某个结点后得到的最大连通分量大小中，删去结点 $v$ 时所得到的值最小．
    3.  树中所有结点到某个结点的距离和中，到结点 $v$ 的距离和最小．

=== "有根树版本"
    1.  当树以结点 $v$ 为根时，任一真子树的大小均不超过原树结点数的一半．
    2.  在所有以某个结点为根时的最大真子树大小中，以结点 $v$ 为根时所得到的值最小．
    3.  在所有以某个结点为根时所有结点的深度和中，以结点 $v$ 为根时深度和最小．

将 $S(x)$ 理解为以 $x$ 为根时的结点深度和，考虑它在树根从结点 $v$ 换为相邻结点 $u$ 时发生的变化．注意到，在树中删去边 $(v,u)$ 后，得到的两个连通分量分别是子树 $T_v^{(u)}$ 和 $T_u^{(v)}$．在换根前后，子树 $T_v^{(u)}$ 中每个结点深度都增加 $1$，子树 $T_u^{(v)}$ 中每个结点深度都减少 $1$，所以，深度和的变化为

$$
\Delta S_{v\to u} = S(u) - S(v) = |T_v^{(u)}| - |T_u^{(v)}| = |T| - 2|T_u^{(v)}|.
$$

所以，定义 1 的条件相当于要求 $\Delta S_{v\to u}\le 0$ 对 $v$ 的所有相邻结点 $u$ 都成立，也就是说，$v$ 是 $S(x)$ 的极小值点．

转而设 $v$ 是 $S(x)$ 的（一个）最小值点（即定义 3），它必然存在，且一定是极小值点．考虑以 $v$ 为根的有根树 $T^{(v)}$．设 $u\neq v$ 是一个非根结点，且从 $v$ 到 $u$ 的有向路径上，结点 $v$ 的后一个结点为 $y$（可能就是 $u$），结点 $u$ 的前一个结点为 $x$（可能就是 $v$）．那么，因为 $T_u^{(x)}\subseteq T_y^{(v)}$，所以有

$$
2|T_x^{(u)}| = 2|T| - 2|T_u^{(x)}| \ge 2|T| - 2|T_y^{(v)}| \ge |T|.
$$

其中，最后一步用到 $v$ 是 $S(x)$ 的极小值点这一事实．此时，有两种情形：

-   存在结点 $u$ 使得 $2|T_x^{(u)}|=|T|$ 成立．此时，根据上述不等式，必然有 $(x,u)=(v,y)$，且 $|T_v^{(u)}|=|T_{u}^{(v)}| = |T|/2$．也就是说，使得等式成立的结点 $u$ 只能有一个，且它必然与 $v$ 相邻．此时，对于所有其他结点 $u'\neq u,v$，必然存在 $x'\sim u'$ 使得 $|T_{x'}^{(u')}| > |T|/2$ 成立．满足条件 1 的结点集合为 $\{v,u\}$．

    注意到，删去任何结点时，得到的连通分量大小之和总是 $|T|-1$，所以，只要有一个连通分量大小不小于 $|T|/2$，它就必然是最大连通分量．因此，对于这种情形，$W(v)=W(u)=|T|/2$，且对于所有 $u'\neq u,v$ 都有 $W(u') > |T|/2$．因此，满足条件 2 的结点集合为 $\arg\min W(x) = \{v,u\}$．

    又因为 $\Delta S_{v\to u} = 0$，所以 $S(v)=S(u)$．因为 $v$ 是最小值点，$u$ 也一定是最小值点．而对于 $u'\neq u,v$ 都存在 $x'\sim u'$ 使得 $|T_{x'}^{(u')}| > |T|/2$，这违反了极小值点需要满足的条件，所以，$u'$ 一定也不是最小值点．因此，满足条件 3 的结点集合为 $\arg\min S(x) = \{v,u\}$．
-   不存在结点 $u$ 使得 $2|T_x^{(u)}|=|T|$ 成立．此时，对于所有结点 $u\neq v$，都存在结点 $x\sim u$ 使得 $|T_x^{(u)}| > |T|/2$．重复前文分析可知，对于所有结点 $u\neq v$，都有 $W(u) > |T|/2$，且 $u$ 不是 $S(x)$ 的极小值点．因此，满足条件 1 的结点只有 $v$，且 $\arg\min W(x)=\arg\min S(x) = \{v\}$．

无论在哪一情形中，满足三个条件的集合都是相同的．这就证明了三个定义是等价的．

性质 2 只需要考虑添加一个叶子结点的情形．这进一步分为两种情形：

-   树 $T$ 只有一个重心 $v$．设 $x$ 为新添加的叶子结点，且在新树中删去结点 $v$ 得到的图 $T\cup\{x\}\setminus\{v\}$ 中，$x$ 所在连通分量为 $B\cup\{x\}$．因为 $v$ 是树 $T$ 的唯一重心，所以 $2|B| < |T|$，也就是 $2|B|+1\le |T|$．进而，有

    $$
    2|B\cup\{x\}| = 2(|B|+1) \le |T| + 1 = |T\cup\{x\}|.
    $$

    因此，$v$ 仍然是新树 $T\cup\{x\}$ 的重心．即使新树的重心不唯一，它也必然是 $v$ 的相邻结点．因此，重心至多移动一条边．
-   树 $T$ 有两个重心 $u,v$．此时，删去 $(u,v)$ 得到的两个连通分量 $T_u^{(v)}$ 和 $T_v^{(u)}$ 大小相等，均为 $|T|/2$．不妨设新添加的叶子结点 $x$ 连接在 $v$ 所在的连通分量 $T_v^{(u)}$ 上．那么，因为

    $$
    |T_v^{(u)}\cup\{x\}| = |T|/2 + 1 > (|T|+1)/2 = |T\cup\{x\}|/2,
    $$

    所以 $u$ 不再是新树的重心．反过来，因为删去 $v$ 后，仍然有大小为 $|T|/2$ 的连通分量 $T_u^{(v)}$，而其他连通分量的大小之和为

    $$
    |T\cup\{x\}| - 1 - |T_u^{(v)}| = |T|/2 \le |T_u^{(v)}|,
    $$

    所以，$v$ 仍然是新树的重心．因为新树的结点数是奇数，重心必然唯一．所以，重心也至多移动一条边．

总结两种情形的分析可以发现，新树的重心一定在旧树的重心与新添加的叶子结点的路径上．

性质 3 可以通过归纳法说明．设 $T$ 和 $T'$ 连接时，新添加的边为 $(x,y)$，且 $x\in T,y\in T'$．不妨设新树的（一个）重心在 $T$ 中．考虑从树 $T$ 开始，将树 $T'$ 中结点逐一添加为其叶子结点的过程．可以归纳地证明，树的（一个）重心始终在连接树 $T$ 的重心与结点 $x$ 的路径上．归纳起点显然．假设直到某一时刻为止，命题仍然成立．设此时重心为 $v$．由性质 2 的分析可知，新树的重心必然在连接新添加结点和当前重心 $v$ 的路径上，又因为它不会移动到树 $T$ 外，所以，只需要考虑路径与树 $T$ 的公共部分，即连接当前重心 $v$ 和结点 $x$ 的路径上．根据归纳假设，$v$ 就在连接树 $T$ 的重心和结点 $x$ 的路径上，所以，新树重心也必然在连接当前重心 $v$ 和结点 $x$ 的路径上．由归纳法可知，命题成立．

性质 4 只需要结合 [重链剖分性质](./hld.md#重链剖分的性质) 即可说明．设树 $T$ 的（一个）重心为 $v$．结点 $v$ 是根结点时，命题显然成立．下面设 $v$ 是非根结点，$u$ 是它的父结点．因为 $|T_u^{(v)}| \le |T|/2$，所以，$v$ 所在子树大小至少是 $|T|/2$．但是，只要它到根结点的路径上经过一次轻边，它所在子树大小将严格小于 $|T|/2$，矛盾．所以，它必然在根结点所在重链上．进而，根据重链的定义，根结点重子结点对应子树中根结点所在重链就是原树中根结点所在重链的一部分；而且，根据性质 3，在重子结点对应子树上添加重子结点及其所有轻子结点对应子树后，重心位置将沿着当前重心和根结点路径移动，所以新重心必然是旧重心的祖先．

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

在 $O(n)$ 时间内可以求出所有子树的重心．