Longest Tree Path

http://wattlebird.github.io/2014/09/21/%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/

求一个自由树的直径。对于直径，《算法导论》第三版 349 页练习 22.2-8 上面这么定义道：

树中所有最短路径的最大值即为树的直径。

这个树由于没有根结点，其实直径这个概念，还是理解为一个连通无向无环图的直径为好。

现在给定如下格式的输入：

8
1 2
1 3
1 4
4 5
3 6
6 7
7 8

第一行是这个图的结点个数，不妨记为 N，以下 N-1 行是 N-1 条边，结点序号按照 1-N 顺序编号。求这个图的直径。

这个输入的输出结果是 6，给出这个示意图就可以看得很清楚：

对于这个问题，最笨的方法就是对每一个结点进行 BFS，因为 BFS 有这个性质：BFS 生成的 广度优先树的每一个结点到达根结点的路径总是最短路。这样，把每一个结点 BFS 一遍就会生成一个该结点到达的最远结点。按照定义取出最长的路径即可。由于 BFS 时间复杂度是 O(N)，这个方法的时间复杂度是O(N2)$O(N^2)$。

其实还有一个更为简便的方法：首先对任意一个结点做 BFS 求出最远的结点，然后以这个结点为根结点再做 BFS 到达另一个最远结点。第一次 BFS 到达的结点可以证明一定是这个图的直径的一端，第二次 BFS 就会达到另一端。下面来证明这个定理。

但是在证明定义之前，先证明一个引理：

引理：在一个连通无向无环图中，x、y 和 z 是三个不同的结点。当 x 到 y 的最短路与 y 到 z 的最短路不重合时，x 到 z 的最短路就是这两条最短路的拼接。

证明：假设 x 到 z 有一条不经过 y 的更短路δ(x,z)$\delta (x,z)$，则该路与δ(x,y)$\delta (x,y)$、δ(y,z)$\delta (y,z)$形成一个环，与前提矛盾。

定理：在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。

证明：假设这条直径是δ(s,t)$\delta (s,t)$。分两种情况：

1. 当出发结点 y 在δ(s,t)$\delta (s,t)$时，假设到达的最远结点 z 不是 s,t 中的任一个。这时将δ(y,z)$\delta (y,z)$与不与之重合的δ(y,s)$\delta (y,s)$拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。
2. 当出发结点 y 不在δ(s,t)$\delta (s,t)$上时，分两种情况：
   1). 当 y 到达的最远结点 z 横穿δ(s,t)$\delta (s,t)$时，记与之相交的结点为 x。此时有δ(y,z)=δ(y,x)+δ(x,z)$\delta (y,z)=\delta (y,x)+\delta (x,z)$。而此时δ(y,z)>δ(y,t)$\delta (y,z)>\delta (y,t)$，故可得δ(x,z)>δ(x,t)$\delta (x,z)>\delta (x,t)$。由1的结论可知该假设不成立。
   
   2). 当 y 到达的最远结点 z 与δ(s,t)$\delta (s,t)$不相交时，记 y 到 t 的最短路首先与δ(s,t)$\delta (s,t)$相交的结点是 x。由假设δ(y,z)>δ(y,x)+δ(x,t)$\delta (y,z)>\delta (y,x)+\delta (x,t)$。而δ(y,z)+δ(y,x)+δ(x,s)$\delta (y,z)+\delta (y,x)+\delta (x,s)$又可以形成δ(z,s)$\delta (z,s)$，而δ(z,s)>δ(x,s)+δ(x,t)+2δ(y,x)=δ(s,t)+2δ(y,x)$\delta (z,s)>\delta (x,s)+\delta (x,t)+2\delta (y,x)=\delta (s,t)+2\delta (y,x)$，显然与题意矛盾。
   

因此定理成立。

9月21日补充：这道题是上一周 hihocoder 上面的一道题。出题者的原意并不是要我们这么做。出题者写了很长的一段提示，但是这段提示的语文表述很差，完全没有抓住重点，导致我花了一个星期的时间也没弄明白他在讲什么。现在所有人的源代码均已公开，可以继续下去了。

出题者的原意是要我们使用这么一个定理：

定理2：树的直径，等于以树直径上任意一点为根的有根树，其左子树的高度+1，再加上其右子树高度+1。

按照这种定理的定义，我们可以设计这样一个程序，对每个结点计算左子树高度+右子树高度+2.这样的时间复杂度是O(n2)$O(n^2)$。由于我们不知道所选取的结点是否是在直径上，所以要进行这样的枚举。显然这会超时。但是根据本文的提示，寻找这种直径的过程其实可以递归化：

1. 在根结点的左子树上；
2. 在根结点的右子树上；
3. 直径经过根结点。

于是我们可以设计这样的程序：选取任意结点为根结点，递归地计算每个结点的高度。在结点内部计算高度的同时，计算以当前结点为根的子树的左子树高度+右子树高度+2，用于更新全局树直径

https://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html

主要是利用了反证法：

假设 s-t这条路径为树的直径，或者称为树上的最长路

现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路

证明：

1    设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则

dis(u,T) >dis(u,s)     且  dis(u,T)>dis(u,t)   则最长路不是s-t了，与假设矛盾

2   设u不为s-t路径上的点

    首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了

    所以现在又有两种情况了：

    1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)

    2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，

    则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾

    附上一张第二种情况的图

     

https://blog.csdn.net/qianguch/article/details/78216860

一棵树的直径就是这棵树上存在的最长路径。 

求法: 

两次dfs或bfs。第一次任意选一个点进行dfs(bfs)找到离它最远的点，此点就是最长路的一个端点，再以此点进行dfs（bfs），找到离它最远的点，此点就是最长路的另一个端点，于是就找到了树的直径。 

证明: 

假设此树的最长路径是从s到t,我们选择的点为u。反证法：假设搜到的点是v。 

1、v在这条最长路径上，那么dis[u,v]>dis[u,v]+dis[v,s],显然矛盾。 

2、v不在这条最长路径上，我们在最长路径上选择一个点为po，则dis[u,v]>dis[u,po]+dis[po,t]，那么有dis[s,v]=dis[s,po]+dis[po,u]+dis[u,v]>dis[s,po]+dis[po,t]=dis[s,t],即dis[s,v]>dis[s,t],矛盾。 

也许你想说u本身就在最长路径，或则其它的一些情况，但其实都能用类似于上面的反证法来证明的。 

综上所述，你两次dfs(bfs)就可以求出最长路径的两个端点和路径长度。 

附练习题: 

1、POJ 1985 Cow Marathon 模板题； 

2、POJ 3310 Caterpillar 需判断出其实是求树的直径，模板运用，不难。