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

    JYY为了省钱,从一个不知名的小吊灯商那里购来一批吊灯,但是他发现并不能直接把这吊灯挂起来:只有一个吊灯能挂在天花板上,而其他所有的灯只能固定的挂在某一个别的吊灯上(可恶的奸商~…好在没有什么吊灯A只能挂在吊灯B上,而吊灯B却也只能挂在吊灯A上的情况)。众所周知,每个吊灯都有其本身的重量,也有一定的承受能力,并且,不是所有的吊灯亮度都一样的。JYY希望能够选出其中的一些吊灯吊起来,每个灯下面所吊的都在其重力承受范围之内,且使所有灯的亮度之和最大,JYY要求你帮他解决这个问题。

    输入格式

    共包含n+1行:
    第一行一个整数n。
    以后的n行每行四个整数t、w、p、q,
    第i+1行的t(t<i)表示第i盏灯只能吊在第t盏灯下面,w表示第i盏灯的重量,p表示第i盏灯所能吊起的最大重力,q表示第i盏灯的亮度。
    注意:第1盏灯的t=0。

    输出格式

    一行,一个整数表示最大的亮度。

    样例输入 1

    5
    0 100 100 100
    1 50 50 50
    1 50 50 50
    2 30 50 60
    2 25 50 50

    样例输出 1

    210

    样例输入 2

    5
    0 20 20 3611
    1 16 6 3291
    1 12 4 8192
    1 3 15 3886
    3 14 1 4222

    样例输出 2

    15689

    提示

    0≤n≤400
    0≤w≤200
    0≤p≤200
    0≤q≤10000


    来源  jsoi2009