【luogu4408】 [NOI2003]逃学的小孩 [动态规划 树的直径]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<stack>
 7 #include<algorithm>
 8 using namespace std;
 9 #define ll long long
10 #define rg register
11 const int N=200000+5,P=9901,inf=0x3f3f3f3f;
12 int n,m,s;ll ans=0,maxl,sa,mm=0;
13 template <class t>void rd(t &x)
14 {
15     x=0;int w=0;char ch=0;
16     while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar();
17     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
18     x=w?-x:x;
19 }
20 
21 int head[N],tot=0;
22 struct edge{
23     int v,nxt;ll w;
24 }e[N<<1];
25 void add(int u,int v,ll w){
26     e[++tot].v=v,e[tot].w=w,e[tot].nxt=head[u],head[u]=tot;
27 }
28 
29 ll a[N],b[N];
30 void dfs(int u,int fa,ll d[])
31 {
32 //    if(d[u]>maxl) sa=u,maxl=d[u];
33     for(rg int i=head[u];i;i=e[i].nxt)
34     {
35         int v=e[i].v,w=e[i].w;
36         if(v==fa) continue;
37         d[v]=d[u]+w;
38         if(d[v]>maxl) sa=v,maxl=d[v];
39         dfs(v,u,d);
40     }
41 }
42 
43 int main()
44 {
45    // freopen("in.txt","r",stdin);
46     //freopen("nocows.out","w",stdout);
47     memset(a,0,sizeof(a));
48     rd(n),rd(m);
49     int u,v;ll w;
50     for(rg int i=1;i<=m;++i)
51     {
52         rd(u),rd(v),rd(w);
53         add(u,v,w),add(v,u,w);
54     }
55     dfs(1,0,a);maxl=0;
56     memset(a,0,sizeof(a));
57     dfs(sa,0,a);ans=maxl,maxl=0;
58     dfs(sa,0,b);
59     for(rg int i=1;i<=n;++i)
60     mm=max(mm,min(a[i],b[i]));
61     printf("%lld",mm+ans);
62     return 0;
63 }