树的直径

在一棵树上，两点之间最短路的最大值成为树的直径。

性质

当边权为正时，以下性质成立

1. 直径的两个端点一定是叶子节点

2. 对于树上任一点$v$，离他最远的点$u$一定是直径的端点

3. 对于分别以$a,b$和$c,d$为直径端点的两棵树，如果增加一条边$e(x,y)$将两棵树合并，那么新树的直径端点$u,v\in\{a,b,c,d\}$

   证明：如果$(a,b)$与$(c,d)$都不是新树的直径，那么新的直径一定通过$e$，那么对于点$x$（或$y$）来说，距离最远的两个点一定在$\{a,b,c,d\}$中。

树的重心

对于树上某一节点$v$，将他转化为整棵树的根后，记其最大子树的大小为$f(v)$。

树的重心$v_i$即为$f(v_i)$最小的点。

换句话说：树的重心是树中最大子树最小的点。

性质

记树的某一重心为$r$

1. 以r根时，所有子树的大小不超过树大小的一半

2. 树的重心至多有2个，若不唯一时，这两个重心相邻。

3. 记函数$dis(x)$为树中所有点到点$x$的距离和，其中$dis(r)$最小。

   如果有两个树根，则他们的$dis$一样。

4. 对于以$u,v$为重心的两棵树，添加一条边合并后，新的树的重心在$(u,v)$上。

5. 在树上添加或删除一个叶节点，重心$r$最多只移动一条边的距离。

参考

树的重心的性质及其证明 (opens new window)