树的直径及其性质与证明

灰太狼 2021-03-30 15:22 568阅读 0赞

# 前言： #

树的直径指树上距离最远的两点间的距离，它在树上问题上有许多应用，往往通过树的直径的性质可以将一个高时间复杂度的解法变为线性求解。对于树上两点间距离通常有三种定义，我们根据这三种情况分别讨论一下它的性质。

# 树的直径的求法： #

树的直径有两种求法，时间复杂度都是$O(n)$。

## 贪心求法： ##

贪心求直径的方法是任意找一个点为根，dfs整棵树找到距离他最远的点$x$，再以这个点$x$为根求出距离它最远的点$y$，$(x,y)$即为直径。证明后面再说。

## DP求法： ##

DP求直径的方法是对于每个点记录这个点子树中的最长链及与最长链处于不同子树中的次长链，用每个点的最长链+次长链更新直径，然后再将最长链上传到父节点更新父节点的最长链或次长链。这种求法适用于所有求树的直径的情况。

# 一、 #

定义两点间距离为两点间路径上的边权和，边权非负。

贪心求直径的方法适用于这种树的直径。

#### 证明： ####

假设确定了直径的一个端点，那么另一个端点一定是距离这个端点最远的点，所以第二次找最远点的贪心一定正确。我们采用反证法，假设第一次从$a$开始找，找到的点是$x$，而存在一个点$u$使得以$u$为根找最远点$v$形成的直径要比以$x$为根找最远点形成的直径长。假设两点间距离用$dis$表示

如果$(x,u)$的路径与$(u,v)$的路径不相交，$dis(x,u)+dis(u,v)$一定比$dis(u,v)$长，假设不成立。

如果$(x,u)$的路径与$(u,v)$的路径相交，假设两路径的另一交点为$y$，那么$dis(x,y)>dis(u,y)$，因为以$a$为根时$x$的深度比$u$的深度深，所以手画一下就能看出来。

### 性质： ###

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

2、距离任意点最远的点一定是直径的一个端点，这个基于贪心求直径方法的正确性可以得出

3、对于两棵树，如果第一棵树直径两端点为$(u,v)$，第二棵树直径两端点为$(x,y)$，用一条边将两棵树连接，那么新树的直径一定是$u,v,x,y,$中的两个点

###### 证明：如果新树直径不是原来两棵树中一棵的直径，那么新直径一定经过两棵树的连接边，新直径在原来每棵树中的部分一定是距离连接点最远的点，即一定是原树直径的一个端点。 ######

4、对于一棵树，如果在一个点的上接一个叶子节点，那么最多会改变直径的一个端点

###### 证明：假设在$x$下面接一个点$y$，直径变成了$(u,x)$,原树直径为$(a,b)$，那么$dis(u,x)>dis(a,b),dis(u,x)=dis(u,y)+1$，即$dis(u,y)+1>dis(a,b)$，如果$dis(u,y)<dis(a,b)$，那么显然不成立；如果$dis(u,y)=dis(a,b)$，那么$(u,y)$也是原树的直径，符合上述结论。 ######

5、若一棵树存在多条直径，那么这些直径交于一点且交点是这些直径的中点

# 二、 #

定义树的直径为两点间路径上边权和+两点点权和，点权可以为负数，边权非负。

这种情况满足贪心求法及上述2、3性质，同样证明一下贪心求法及性质2：

可以发现性质二满足的原因是贪心求法的成立，所以只需要证明贪心的成立即可。

假设第一次dfs以$a$为根，深度+点权的最大点为$x$，假设存在一个更优点$u$使得从$u$开始找最远点$y$形成的直径比从$x$找最远点形成的直径长，令$x$与$u$到根的路径不交集部分长度分别为$l(x),l(u)$，两点点权分别为$v(x),v(u)$，那么$l(x)+v(x)>l(u)+v(u)$。

如果$(u,y)$与$(x,u)$不相交，那么显然$v(x)+l(x)+l(u)>v(u)$，$dis(x,u)+dis(u,y)+v(x)+v(y)>dis(u,y)+v(u)+v(y)$

如果$(u,y)$与$(x,u)$相交，假设两路径交点为$b$，那么也可以得出$dis(b,x)+v(x)>dis(b,u)+v(u)$的结论

# 三、 #

定义树的直径为两点间路径上边权和，边权有负数。