Problem 24419 --R组织

24419: R组织

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 51  Solved: 19
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][348kb]

Description

现在某组织中(记作R)有n个人,他们的联络网形成一棵以Saltless为根的树,有边相连代表两人可以直接联络。
每个人有一个代号,Saltless代号为1,且除Saltless外每个人的父节点的代号小于他自己的代号。
由于某些原因,Saltless给R的成员分别下达紧急任务,R需要分成m组行动,每个组必须满足如下条件:
1、每个组员仅分在本组中
2、至少有一个组员
3、任意两个组员无需通过本组外的人就可以联络(但可以通过本组组员进行联络)
每个人有一个能力指数,一个组的能力指数是全组人能力指数之和。
对于任意一种正确的分组,平均度就是m组中最小能力指数。为了分组较为平均,Saltless希望平均度尽可能大。

Input

第一行为三个数:n,m,和Saltless的能力指数(1<=m<=n<=10000)。
接下来n-1行,每行两个数:此人的父节点代号和他的能力指数(能力指数值为正整数,不超过30,行数就是他本身的代号)

Output

一个数,表示最大的平均度。

Sample Input

7 2 2
1 4
1 5
2 1
2 2
3 4
4 3

Sample Output

10

HINT

【Hint】

分组:{1,3,6},{2,4,5,7}

Source

[Submit][Status]