22.2-7
很显然数的直径就是树的最长简单路。
先进行一次BFS，然后再从BFS的终点再进行一次BFS得到的最长路径就是直径。进行了两次BFS，所以复杂度还O(E+V)。
参考自：http://www.cnblogs.com/hanyulcf/archive/2010/10/23/tree_radius.html
树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；
原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度
#include<iostream>
1. #include<queue>
2. #define INF 999999
3. #define M 2002
4. using namespace std;
5. int n;
6. int maxx;
7. int map[M][M],sum[M];
8. bool flag[M];
9. int bfs(int begin){
10. queue<int>f;
11. int i,m,k,key;
12. maxx=0;
13. memset(flag,false,sizeof(flag));
14. f.push(begin);
15. while(!f.empty()){
16. k=f.front();
17. for(i=1;i<=n;i++){
18. if(map[k][i]!=INF&&!flag[i]){
19. flag[i]=true;
20. f.push(i);
21. sum[i]=sum[k]+map[k][i];
22. if(sum[i]>maxx) { maxx=sum[i];key=i; }
23. }
24. }
25. f.pop();
26. }
27. return key;
28. }
29. int main()
30. {
31. int i,j,k,dis,key,cas;
32. scanf("%d",&cas);
33. while(cas--){
34. scanf("%d",&n);
35. for(i=1;i<n;i++)
36. for(j=i+1;j<=n;j++)
37. map[i][j]=map[j][i]=INF;
38. for(i=1;i<n;i++){
39. scanf("%d%d%d",&j,&k,&dis);
40. map[j][k]=map[k][j]=dis;
41. }
42. sum[1]=0;
43. key=bfs(1);
44. sum[key]=0;
45. key=bfs(key);
46. printf("%d\n",maxx);
47. }
48. //system("pause");
49. }