树的直径

树的直径：树的直径是指树的最长简单路。

求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；

原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点

证明:1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)

　　2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
　　所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

下面是我的bfs。。比较丑陋～

 1 void bfs(int pos,int deepth){
 2     if(deepth > deep){
 3         deep = deepth;
 4         start = pos;
 5     }
 6     vis[pos] = 1;
 7     for(int i=0;i<tran[pos].size();i++){
 8         if(!vis[tran[pos][i]]) bfs(tran[pos][i],deepth+1);  // 设每条边长度都是1，如果权值不一样则要加上权值
 9     }
10     return ;
11 }

求树的直径的话，我现在遇到的情况还比较少，下面有一道例题：Codeforces 734E