TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2318
  • Problem
  • P2318没有上司的晚会
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

    第1行一个整数N(1<=N<=6000)表示公司的人数。
    接下来N行每行一个整数。第i行的数表示第i个人的气氛值x(-128<=x<=127)。
    接下来每行两个整数L,K。表示第K个人是第L个人的上司。
    输入以0 0结束。

    Output Format

    一个数,最大的气氛值和。

    Sample Input

    7
    1
    1
    1
    1
    1
    1
    1
    1 3
    2 3
    6 4
    7 4
    4 5
    3 5
    0 0

    Sample Output

    5


    Source  ural 1039