TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2318
  • 题目
  • P2318没有上司的晚会
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    有个公司要举行一场晚会。
    为了能玩得开心,公司领导决定:如果邀请了某个人,那么一定不会邀请他的上司
    (上司的上司,上司的上司的上司……都可以邀请)。 
    每个参加晚会的人都能为晚会增添一些气氛,求一个邀请方案,使气氛值的和最大。

    输入格式

    第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


    来源  ural 1039