题目描述(ID:12248)
标题: 周年纪念日
标签: 动态规划 树形DP
详情:
长郡中学校长打算举行建校100周年的晚会。学校的职员是分等级的,也就是说,职员之间的上下级关系组成一棵以校长作为根的树。校长要亲自邀请一些职员参加晚会。同时校长亲自到场,欢庆这个节日。职员用1到N之间的整数编号,人事处给出了每个职员的搞笑指数。如果一个人和他上司一起参加,那么便可能产生麻烦。为了使晚会的每个参加者都高兴,校长不会同时邀请一个职员和他的顶头上司。
你的任务是给出一个客人的列表,使得客人的搞笑指数之和最大。
输入格式:
第一行是一个整数N(1<=N<=6000)。下面的N行每行是相应编号职员的搞笑指数。这个数的范围是-128..127。下面是职员的关系树。每行的格式是:,意思是第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
登录并解答