题意：
给定一棵树， 求树的直径。
分析：
两种方法：
1.两次bfs， 第一次求出最远的点， 第二次求该点的最远距离就是直径。
2.同hdu2196的第一次dfs， 求出每个节点到子树的最长距离和次长距离， 然后某个点的最长+次长就是直径。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std; const int maxn = + ;
const int inf = 1e9 + ;
int Max[maxn];// 最大距离
int sMax[maxn];// 次大距离
struct Edge {
int v, d;
};
vector<Edge> G[maxn];
int N = ;
void init() {
for(int i = ; i < maxn; i ++) {
G[i].clear();
}
}
void dfs1(int u, int pre) {//更新u本身
Max[u] = sMax[u] = ;
for(int i = ; i < G[u].size(); i++) {
int v = G[u][i].v, d = G[u][i].d;
if(v == pre)
continue; //不经过父亲， 只搜索子树
dfs1(v, u); //一直搜到叶子再回溯， 因为是根据孩子的Max更新自己的Max
if(sMax[u] < Max[v] + d) { //如果u的次长距离 < 到v的距离 + v的最大距离
//更新距离
sMax[u] = Max[v] + d;
if(sMax[u] > Max[u]) { //如果次长距离大于最长距离， 交换二者位置
swap(sMax[u], Max[u]);
}
}
}
} int u, v, d;
int main() {
while(cin >> u >> v >> d) {
N++;
G[u].push_back((Edge) {v,d});
G[v].push_back((Edge) {u,d});
}
dfs1(, -); int ans = -inf;
for(int i = ; i <= N; i++) {
ans = max(ans, Max[i] + sMax[i]);
}
cout << ans << "\n";
return ;
}