1 //树形DP求树的直径

 2 #include<bits/stdc++.h>

 3 using namespace std;

 4 const int N=500005,M=500005;

 5 int n,m,tot,ans;

 6 int f1[N],f2[N];//以u为根的子树的最大值和次大值

 7 int head[N],to[M*2],w[M*2],nxt[M*2];

 8

 9 void add(int x,int y,int z){

10     nxt[++tot]=head[x];

11     head[x]=tot;

12     to[tot]=y;

13     w[tot]=z;

14 }

15

16 void dp(int u,int fa){

17     for(int i=head[u];i;i=nxt[i]){

18         int v=to[i];

19         if(v==fa) continue;

20         dp(v,u);

21         if(f1[u]<f1[v]+w[i]){

22             f2[u]=f1[u];

23             f1[u]=f1[v]+w[i];

24         }

25         else if(f2[u]<f1[v]+w[i])

26             f2[u]=f1[v]+w[i];

27         ans=max(ans,f1[u]+f2[u]);

28     }

29 }

30

31 int main(){

32     scanf("%d",&n);

33     int x,y,z;

34     for(int i=1;i<n;i++){

35         scanf("%d%d%d",&x,&y,&z);

36         add(x,y,z);add(y,x,z);

37     }

38     dp(1,0);

39     printf("%d\n",ans);

40     return 0;

41 }