2141: 宝典2第十一章鸿门宴
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:4
Solved:3
Description
【问题描述】鸿门宴(party.cpp/c/pas)TOJ 1039
修罗王欲瘫痪天顶星人军队的建制,于是设计邀请天顶星人军官在一个城堡参加一场盛大的晚会。他的借口是为了让到会的每个人不受他的直接上司约束而能玩得开心,所以晚会的安排是:如果邀请了某个人,那么一定不会再邀请他的直接的上司,但该人的上司的上司,上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。
已知每个参加晚会的天顶星人都有一定的价值,求一个邀请方案,使价值的和最大。
【输入格式】
第1行一个整数N(1≤N≤6000)表示天顶星人的人数。
接下来N个整数。表示第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