TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3504
  • 题目
  • P3504迷宫
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    样例输入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:
    146
    样例输出2:
    158

    提示

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


    来源  2013 Multi-University Training Contest 2