树的重心与同构：算法竞赛中的核心概念解析

1. 树的重心：概念与性质解析

树的重心是图论中一个非常重要的概念，在算法竞赛和实际应用中都有着广泛的使用场景。理解重心的定义和性质，能够帮助我们更好地解决树结构相关的问题。

1.1 重心的三种等价定义

在实际应用中，树的重心可以通过三种不同的方式来定义，这三种定义在本质上是完全等价的：

1. 最小深度和定义：寻找一个节点，使得所有节点到该节点的深度之和最小。这个定义直观地体现了重心的"中心性"特征。

2. 最小最大子树定义：寻找一个节点，使得以该节点为根时，最大的子树的大小最小。这个定义强调了重心的平衡特性。

3. 子树大小限制定义：寻找一个节点，使得以该节点为根时，所有子树的大小不超过n/2（n为树的总节点数）。这个定义给出了重心的一个明确判定条件。

提示：在实际应用中，第三个定义通常是最容易验证的，因此常被用作重心的判定标准。

1.2 重心等价性的数学证明

我们可以通过动态规划的转移式来证明这三种定义的等价性。核心转移式为：

dp[u] = dp[v] + n - 2 × siz[v]

其中：

• dp[u]表示以u为根时所有点到u的深度和
• siz[v]表示u的子节点v对应的子树节点数
• n为树的总节点数

从转移式可以推导出dp[v] - dp[u] = n - 2 × siz[v]，这个关系式揭示了重心移动时深度和的变化规律。

分析两种情况：

1. 当存在子节点v使得siz[v] > n/2时，向v方向移动会减小深度和
2. 当所有子节点v都满足siz[v] ≤ n/2时，向任何方向移动都会增大深度和

这个分析不仅证明了三种定义的等价性，还给出了寻找重心的有效方法：从任意节点出发，总是向最大子树方向移动，直到找到满足条件的节点。

1.3 重心的关键性质

树的重心具有以下几个重要性质，这些性质在解决实际问题时非常有用：

1. 重心数量：一棵树的重心数量要么是1个，要么是2个。当存在2个重心时，它们必定是相邻的节点（即通过一条边直接相连）。

2. 动态变化：当树的结构发生微小变化（如增加或删除一个叶子节点）时，重心最多只会移动一条边的距离。这个性质在动态维护树结构时特别有用。

3. 合并性质：将两棵树合并后，新树的重心一定位于原来两棵树重