1736: 周年庆宴会
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:41
Solved:18
Description
某大学有N个职员,举办周年庆宴会,编号1到N。他们有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。每个人都有一个欢乐值,为了让气氛更好,要求在这N个人中选一些人去参加宴会,并且选出的这些人中任意两个人之间都没有直接上司或直接下属关系,求选出人的最大欢乐值。
Input
输入第一行一个整数N。(1≤N≤6000)。接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)
接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。
接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。
Output
输出1行,一个整数表示最大的快乐指数。
Sample Input Copy
7
3
1
2
1
1
2
1
2 1
3 1
4 2
5 2
6 3
7 3
Sample Output Copy
8
HINT
1≤n≤6*10^3; -128≤Ri≤127; 1≤l,k≤n 。且给出的关系一定是一棵树。