首先是树的直径的一个定理：
第一步：从带权树上任意一点u出发，搜索到的距离最远的一个点必定是树的直径s-t的一端（s或t）；
第二步：从搜到的点（s或t）开始搜索，搜索到的最远的点就是树的直径的另一端（t或s）。
我在某全球最大的中文搜（guang）索（gao）网站上搜了很多证明，都没有弄懂，最后队友亲自过来证明给我看才弄懂了，这里记录一下。
第二步非常简单，如果已经确定了直径的一端，那么另一端一定是离它最远的那个点。
接下来用反证法证明第一步。其中dis(i, j)表示点i到点j的树上距离。
假设树的直径为s-t，随机取到了一个点u，并从u开始搜索最远的点。
因为s和t是对称的，不妨设dis(u, s) <= dis(u, t)
假设我们从u开始搜索到了v，则v是到u最远的一个点
若v不是s或t中的一个：
则必有dis(u, v) > dis(u, t) >= dis(u, s)
1、s-t与u-v相交：
假设x是s-t与u-v相交部分中最靠近u的点（如下图所示）;
或 
因为左右是对称的，不妨只考虑左边，
则：
dis(u, v) = dis(u, x) + dis(x, v)
dis(s, t) = dis(s, x) + dis(x, t)
因为v是从u开始搜索到达的最远点：
所以dis(u, v) > dis(u, s)
=> dis(u, x) + dis(x, v) > dis(u, x) + dis(x, s)
=> dis(t, x) + dis(x, v) > dis(t, x) > dis(x, s)
=> dis(t, v) > dis(t, s)
矛盾！
2、s-t与u-v不相交：
因为v是从u出发搜到的最远点，dis(u, t) < dis(u, v);
所以有：dis(s, t) < dis(u, s) + dis(u, t) < dis(u, s) + dis(u, v) = dis(s, v)
即dis(s, t) < dis(s, v)
矛盾！
1、2都矛盾了，说明若v不是s或t中的一点的情况是不存在的，所以v必然是s或t中的一点。