华师一附中OI组

标题: saltless [打印本页]

作者: admin 时间: 2018-9-3 17:59
标题: saltless
现在某组织中（记作R）有n个人，他们的联络网形成一棵以Saltless为根的树，有边相连代表两人可以直接联络。
每个人有一个代号，Saltless代号为1，且除Saltless外每个人的父节点的代号小于他自己的代号。
由于某些原因，Saltless给R的成员分别下达紧急任务，R需要分成m组行动，每个组必须满足如下条件：
1、每个组员仅分在本组中
2、至少有一个组员
3、任意两个组员无需通过本组外的人就可以联络（但可以通过本组组员进行联络）
每个人有一个能力指数，一个组的能力指数是全组人能力指数之和。
对于任意一种正确的分组，平均度就是m组中最小能力指数。为了分组较为平均，Saltless希望平均度尽可能大。
【格式】
输入文件第一行为三个数：n,m,和Saltless的能力指数（1<=m<=n<=10000）。
接下来n-1行，每行两个数：此人的父节点代号和他的能力指数（能力指数值为正整数，不超过30，行数就是他本身的代号）
输出格式：一个数，表示最大的平均度。
SAMPLE INPUT (organ.in)
7 2 2
1 4
1 5
2 1
2 2
3 4
4 3
SAMPLE OUTPUT (organ.out)
10
【Hint】
分组：{1,3,6},{2,4,5,7}

欢迎光临华师一附中OI组 (http://hsyit.cn/)