Universal Online Judge
UOJ
时间限制:1 s
空间限制:32 MB
区间DP、树形DP
R. 没有上司的晚会
【背景】
有个公司要举行一场晚会。为了能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会邀请他的上司（上司的上司，上司的上司的上司……都可以邀请）。
【问题描述】
每个参加晚会的人都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。
【输入格式】
第1行一个整数N（1<=N<=6000）表示公司的人数。
接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。
【输出格式】
一个数，最大的气氛值和。
【输入样例】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
【输出样例】
5
[title]Source[/title]
[link=exerciseproblems?source=Ural+1039]Ural 1039[/link]