1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,long long>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n,m;
ll dis[MAXN];
bool vis[MAXN];
queue<int>que;
pii bfs(int x){
inc(i,1,n)dis[i]=vis[i]=0;
que.push(x);vis[x]=1;
while(!que.empty()){
int y=que.front();que.pop();
link(y){
if(!vis[j->t])vis[j->t]=1,dis[j->t]=dis[y]+j->v,que.push(j->t);
}
}
pii pos=mp(x,0);
inc(i,1,n)if(dis[pos.first]<dis[i])pos=mp(i,dis[i]);
return pos;
}
int fa[MAXN];
void dfs(int x,int pre){
fa[x]=pre;
link(x)if(j->t!=pre)dfs(j->t,x);
}
int p[MAXN];ll sum[MAXN];
void _dfs(int x,int y){
int k;
if(vis[x])k=x;else k=y;
p[x]=k;
link(x)if(j->t!=fa[x])sum[j->t]=sum[x]+j->v,_dfs(j->t,k);
}
int main(){
n=read();m=read();
int x,y,z;
inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
pii t1=bfs(1);
pii t2=bfs(t1.first);
ll ans=t2.second;
dfs(t1.first,0);x=t2.first;
inc(i,1,n)vis[i]=0;
while(x){vis[x]=1;x=fa[x];}
_dfs(t1.first,t1.first);
ll maxx=0;
inc(i,1,n)maxx=max(maxx,sum[i]-sum[p[i]]+min(sum[p[i]]-sum[t1.first],sum[t2.first]-sum[p[i]]));
printf("%lld\n",maxx+ans);
}
|