P3408 恋爱

    • 90通过
    • 370提交
  • 题目提供者 BDF1
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小A爱上了小B!!!可是小A相对小B太弱,所以她当然不会同意小A的请求。小A苦苦追求,最终小B就提这样的条件:

    小B有n个下属(不包括小B)组成了树状结构,小B在顶端,其他人都有一个直属上司。小B编号0,其他人编号1~n。对于第i人,如果这个人没有下属,那么小A可以给他Ai元钱,则他会向他的直属上司写一封信,表示小A向小B求爱,如果他的直属下属有不小于T分之Ai的人写信表示小A向小B求爱,那么他也会向他的直属上司写一封信,表示小A向小B求爱。如果小B的直属下属有不小于T分之C的人写信表示小A向小B求爱,那么她会同意小A的请求。

    请问小A至少需要给多少钱才会让小B同意小A的求爱。

    输入输出格式

    输入格式:

    第一行三个整数n、T、C。

    然后n行,第i行两个整数Bi、Ai,Bi表示i的直属上司,保证Bi<i。

    输出格式:

    需要给的钱数。

    输入输出样例

    输入样例#1: 复制
    14 5 3
    0 3
    0 3
    1 10
    1 10
    2 3
    2 10
    2 3
    5 10
    7 10
    5 10
    7 10
    5 10
    7 10
    5 10
    输出样例#1: 复制
    50

    说明

    对于20%的数据没有直属下属的人数<=15

    对于40%的数据n<=2000

    另有10%的数据Bi=0

    另有10%的数据C=1且对于有直系下属的人T/Ai>n

    另有10%的数据Bi=i-1

    对于100%数据n<=500000 T<=10亿 Bi<i 0<Ai<=T

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。