[Tyvj 1052] 沒有上司的舞會

沒有上司的舞會

時間: 1000ms / 空間: 131072KiB / Java類名: Main

描述

Ural大學有N個職員，編号為1~N。他們有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直接上司。每個職員有一個快樂指數。現在有個周年慶宴會，要求與會職員的快樂指數最大。但是，沒有職員願和直接上司一起與會。

輸入格式

第一行一個整數N。(1<=N<=6000)

接下來N行，第i+1行表示i号職員的快樂指數Ri。(-128<=Ri<=127)

接下來N-1行，每行輸入一對整數L,K。表示K是L的直接上司。

最後一行輸入0,0。

輸出格式

輸出最大的快樂指數。

測試樣例1

輸入

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

輸出

5

題解

dp[i,1]表示選i點的最大值,dp[i,0]表示不選i點的最大值

dp[i,1]=∑dp[son[i],0]

dp[i,0]=∑(dp[son[i],1],dp[son[i],0])max+x[i]

其實樹形DP就是找到父節點與子節點之間取那個,或者取幾個的問題,用DFS遞歸着考慮的

var
 w:array[..,..]of longint;
 x,y:array[..]of longint;
 dp:array[..,..]of longint;
 i,j,k:longint;
 n,len,a,b:longint;
procedure init(a,b:longint);
begin
 w[len,]:=b;
 if w[a,]=
 then w[a,]:=len else w[w[a,],]:=len;
 w[a,]:=len; inc(len);
end;

function max(a,b:longint):longint;
begin
 if a>b then exit(a) else exit(b);
end;

procedure dfs(a:longint);
var tt:longint;
begin
 dp[a,]:=x[a]; dp[a,]:=;
 if w[a,]= then exit;
 tt:=w[a,];
 while tt<> do
  begin
   dfs(w[tt,]);
   inc(dp[a,],dp[w[tt,],]);
   inc(dp[a,],max(dp[w[tt,],],dp[w[tt,],]));
   tt:=w[tt,];
  end;
end;

begin
 readln(n); len:=n+; fillchar(y,sizeof(y),);
 for i:= to n do
  readln(x[i]);
 for i:= to n- do
  begin readln(a,b); init(b,a); inc(y[a]); end;
 for i:= to n do
  if y[i]= then begin a:=i; break; end;
 dfs(a);
 writeln(max(dp[a,],dp[a,]));
end.