题目描述
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e4+10, M = N*2;//M表示边的数量
int h[M], e[M], ne[M], w[M], idx;
bool st[N];
int d;//树的最大直径
void add(int a, int b, int c){
e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}
int dfs(int u){
st[u] = 1;
int d1 = 0, d2 = 0;//分别记录最大长子路径和次大长子路径
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(st[j]) continue;
int t = dfs(j) + w[i];
if(t >= d1){d2 = d1; d1 = t;}//if(t > d1) {d1 = t; d2 = d1;} WA
else if(t > d2) d2 = t;
}
d = max(d, d1 + d2);
return d1;//缺省,WA
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
memset(h, -1, sizeof h);
int n; cin>>n;
while(n--){
int a, b, c; cin>>a>>b>>c;
add(a, b, c); add(b, a, c);
}
dfs(1);
cout<<d;
return 0;
}