Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 树形DP……水过。

Posted by 597100700 at 2011-10-07 22:18:11 on Problem 1985
```var a,b,c,d,e,m,n,sum,max:longint;
f1,f2:array[0..100000]of longint;
list,next,cost,toit:array[0..1000000]of longint;
ch:char;
procedure make(i,j,k:longint);
begin
inc(sum);
toit[sum]:=j;
next[sum]:=list[i];
cost[sum]:=k;
list[i]:=sum;
end;
procedure dfs(i,j:longint);
var ii,jj,kk:longint;
begin
f1[i]:=0;f2[i]:=0;
ii:=list[i];
while ii<>0 do
begin
if toit[ii]<>j then
begin
dfs(toit[ii],i);
if f1[toit[ii]]+cost[ii]>f1[i] then
begin
f2[i]:=f1[i];
f1[i]:=f1[toit[ii]]+cost[ii];
end
else if f1[toit[ii]]+cost[ii]>f2[i] then f2[i]:=f1[toit[ii]]+cost[ii];
end;
ii:=next[ii];
end;
end;
begin
for a:=1 to m do
begin
make(b,c,d);
make(c,b,d);
end;
dfs(1,0);
for a:=1 to n do
if f1[a]+f2[a]>max then
max:=f1[a]+f2[a];
writeln(max);
end.```

Followed by: