TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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