TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3504
  • 問題
  • P3504迷宫
    制限 : 時間制限 : 10000 MS   メモリ制限 : 165536 KB
    問題説明

    迷宫里有 N(编号 0 到 N-1)个房间,任意两个房间之间有且仅有一条路径可以到达。每个房间里面都 有一个礼包,如果你进入了这个房间,你将得到这个礼包。当你离开一个房间后,你就不能再次进入这 个房间了。但是,有的房间里面有陷阱,当你取得礼物后,你就会被困住一会。你可以任意选择一个房 间作为起点,当你没有房间可去或者被困住了 C 次,游戏就结束了。每个礼包都有一定的价值,何老板 希望得到的礼包价值总和尽可能大,问这个最大值是多少?

    入力形式

    第一行,两个整数 N 和 C。
    接下来 N 行,每行两个整数,表示该房间的礼物的价值和是否有陷阱,0 表示没有,1 表示有。
    接下来 N-1 行,每行两个整数 A 和 B,表示 A 和 B 间有道路直接相连。

    出力形式

    一行,一个整数,表示所求答案。

    サンプル入力 1

    样例输入1:
    3 1 
    23 0 
    12 0 
    123 1
    0 2 
    2 1

    样例输入:
    3 2
    23 0 
    12 0 
    123 1
    0 2 
    2 1

    サンプル出力 1

    样例输出1:
    146
    样例输出2:
    158

    サンプル入力 2

    10 3
    468 0
    501 0
    725 0
    359 0
    465 0
    146 1
    828 1
    492 0
    943 0
    437 1
    4 2
    3 5
    2 7
    6 9
    5 8
    6 1
    2 6
    9 3
    1 0

    サンプル出力 2

    3014

    ヒント

    2 <= N <= 50000
    1 <= C <=3


    ソース  2013 Multi-University Training Contest 2