PID724 / 进击的JC
题目描述

【背景描述】JC靠着你对他的帮助,站在了了邪恶的DZY面前,但是邪恶的DZY却挟持了JC的GF并且带着他的机器人们在工厂外的空地上摆出阵势想用武力打败JC。

【题目描述】DZY在空地上摆出了他潜心研究的树形阵。即他的N个机器人摆成了一棵树,每个机器人都会为他的父机器人挡子弹,所以说,JC必须要打掉某个机器人的所有子机器人才能进攻这个机器人。最开始JC只能攻打处在叶子上的机器人。而由于DZY给每个机器人的配置不同,JC在攻打每个机器人所要损失的生命值是不同。由于DZY的机器人可能有很多,所以JC损失的血也会很多。所幸的是,JC可以开挂!在他大神级别的外挂下,他的血被调到了无限。但是,尽管JC不会被打死,但是他必须一个一个叶子节点打过来,这实在是太累了。不过JC在出发前已经向MK学习了分身的技术。就是说可以分身成为K个分身。他可以控制分身去攻打不同的叶子节点。当一个可造成伤害为Ai的机器人同时受到L个分身的攻击时, JC总共收到的伤害是Ai/L向上取整。我们可以把所有攻打同一个节点分身看为一股分身。当然,作为大神,JC有自己的大超。每一股分身每收到P点伤害,他们就会得到P的怒气值。当一股分身的怒气值超过Q时,这股分身便可以消耗掉自己所有的怒气值不受到任何伤害地摧毁接下来要攻打的节点。保证攻打同一个节点的子节点的所有分身都会同时在父节点会合,此时他们的怒气值会累加。尽管JC不会死亡,但是他受到伤害的时候会感到疼痛。所以他还是想请教你如何攻打才能在摧毁所有机器人的情况下使他丧失的生命值最少。

输入格式

第一行是三个整数N,K,Q,其意义和题目描述中的相同。接下来N行第i行是两个数Ai和Fi,表示第i个机器人可以造成的伤害值以及它的父机器人的编号。处于根位置的机器人的父节点编号为0.

输出格式

仅一行,表示JC最小损失的生命值。

样例输入
样例输出
注释

【样例解释】

第3号和第4号的机器人处于叶子位置。JC派1个分身攻打3,2个分身攻打4,所受到的总伤害为6,总怒气为6,接下来攻打机器人2,不发动大超,受到伤害为1,总怒气为6.对于机器人1,JC发动大超,不受到伤害。

【数据范围 】

30%的数据 N,Ai<=5且均为整数

60%的数据N,Ai<=10且均为整数

100%的数据N,K,Q<=50且均为整数,Ai为小于2^16的正实数

提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论