1509: [NOI2003]逃学的小孩 - BZOJ

 1 const
 2     maxn=200200;
 3 var
 4     first,u:array[0..maxn]of longint;
 5     next,last,w:array[0..maxn*2]of longint;
 6     f:array[0..maxn,0..3]of int64;
 7     n,m,tot:longint;
 8     ans:int64;
 9 
10 procedure insert(x,y,z:longint);
11 begin
12     inc(tot);
13     last[tot]:=y;
14     next[tot]:=first[x];
15     first[x]:=tot;
16     w[tot]:=z;
17 end;
18 
19 procedure up(var x:int64;y:int64);
20 begin
21     if x<y then x:=y;
22 end;
23 
24 procedure new(x:longint;y:int64);
25 begin
26     if y>f[x,0] then
27       begin
28         f[x,2]:=f[x,1];
29         f[x,1]:=f[x,0];
30         f[x,0]:=y;
31       end
32     else
33       if y>f[x,1] then
34         begin
35           f[x,2]:=f[x,1];
36           f[x,1]:=y;
37         end
38       else up(f[x,2],y);
39 end;
40 
41 procedure dfs(x,fa:longint);
42 var
43     i:longint;
44 begin
45     i:=first[x];
46     while i<>0 do
47       begin
48         if last[i]<>fa then
49         begin
50           dfs(last[i],x);
51           u[last[i]]:=w[i];
52           new(x,f[last[i],0]+w[i]);
53         end;
54         i:=next[i];
55       end;
56 end;
57 
58 function get(x,y,z:int64):int64;
59 begin
60     exit(x+y*2+z);
61 end;
62 
63 procedure dfs2(x,fa:longint);
64 var
65     i:longint;
66 begin
67     if f[x,0]+u[x]=f[fa,0] then new(x,f[fa,1]+u[x])
68     else new(x,f[fa,0]+u[x]);
69     up(ans,get(f[x,0],f[x,1],f[x,2]));
70     i:=first[x];
71     while i<>0 do
72       begin
73         if last[i]<>fa then dfs2(last[i],x);
74         i:=next[i];
75       end;
76 end;
77 
78 procedure main;
79 var
80     i,x,y,z:longint;
81 begin
82     read(n,m);
83     for i:=1 to m do
84       begin
85         read(x,y,z);
86         insert(x,y,z);
87         insert(y,x,z);
88       end;
89     dfs(1,0);
90     dfs2(1,0);
91     write(ans);
92 end;
93 
94 begin
95     main;
96 end.