← 返回题目列表

Codeforces · 414/D

D. Mashmokh 和水箱

中文机器翻译题面 查看原题

Mashmokh 正在玩一个新游戏。一开始他有 k 升水和 p 个硬币。此外,他还有一棵由 m 个顶点组成的有根树(无向连接的无环图)。树的每个顶点都包含一个水箱,该水箱一开始是空的。

游戏开始时,Mashmokh 选择一些(不超过 k)个水箱(除了根)并向每个水箱中倒入 1 升水。然后执行以下过程,直到水箱中没有水为止。

- 该过程由几个步骤组成。
- 在每一步开始时,Mashmokh都会打开所有坦克的门。然后,Mashmokh 在此移动期间关闭一些坦克的门(不允许他在根部关闭坦克的门)。我们将某个关着门的水箱中的升数表示为 w,Mashmokh 在此移动过程中为关闭该水箱支付 w 个硬币。
- 让我们用 x1, x2, ..., xm 表示按深度排序(非递减)的树顶点列表。应按顺序一一考虑此列表中的顶点。首先,顶点 x1(即根本身)被清空。然后对于每个顶点 xi (i > 1),如果它的门关闭,则跳过该顶点,否则将所有水从顶点 xi 的水箱移动到其父亲的水箱(即使父亲的水箱关闭)。

假设进行了 l 次移动,直到树变空。让我们用 wi 来表示第 i 次移动后根池内的水量,那么 Mashmokh 将赢得 max(w1, w2, ..., wl) 美元。 Mashmokh 想知道通过玩上述游戏他最多可以赢得多少美元。他要求你为他找到这个价值。

输入

输入的第一行包含三个空格分隔的整数 m、k、p(2 ≤ m ≤ 105;0 ≤ k、p ≤ 109)。

以下 m - 1 行中的每一行都包含两个以空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ m; ai ≠ bi) — 树的边。

考虑树的顶点编号从 1 到 m。树的根编号为 1。

输出

输出一个整数,即 Mashmokh 要求您查找的数字。

示例

输入 #1

10 2 1
1 2
1 3
3 4
3 5
2 6
6 8
6 7
9 8
8 10

输出 #1

2

输入 #2

5 1000 1000
1 2
1 3
3 4
3 5

输出 #2

4

注意

第一个示例中的树如下图所示。黑色、红色、蓝色分别对应有 0、1、2 升水的顶点。

获得最大金钱量的一种方法是在顶点 3 和 4 中各放入 1 升水。开始状态如下图所示。

然后在第一步中,Mashmokh 将支付一个代币来关闭第三个顶点坦克的门。第一次移动后的树如下图所示。

第二次移动后,根部有2升水,如下图所示。