CF414D Mashmokh and Water Tanks

Mashmokh 正在玩一个新游戏。一开始他有 $k$ 升水和 $p$ 枚硬币。此外，他还有一棵有根树（无向连通无环图），共包含 $m$ 个结点。每个结点上都有一个一开始为空的水箱。 游戏的开始，Mashmokh 可以选择这些水箱中的一些（不超过 $k$ 个，且不能选择根结点的水箱），向它们每个倒入恰好 $1$ 升水。然后，进行如下流程，直到所有水箱中都没有水为止。 - 该流程包含若干步。 - 每一步开始时，Mashmokh 会打开所有水箱的门。接着，他可以选择关闭部分水箱的门（不能关闭根节点的水箱门），在本次操作中被关闭的水箱门会保持关闭。假设某水箱门被关闭且箱中有 $w$ 升水，Mashmokh 需要为关闭该水箱门支付 $w$ 枚硬币。 - 记 $x_1, x_2, ..., x_m$ 为以深度的非递减顺序排序的树的结点序列。需要按照此顺序依次处理每个结点。首先，$x_1$（即根结点）会被清空水。然后对于每个结点 $x_i$（$i>1$），如果它的门被关闭则跳过，否则将该结点水箱中的所有水倒入它父亲结点的水箱（即使父亲结点门也被关闭）。 假设整个过程中总共进行了 $l$ 步，我们记第 $i$ 步结束后根结点水箱中的水量为 $w_i$，那么 Mashmokh 最终可以获得 $\max(w_1, w_2, ..., w_l)$ 美元。Mashmokh 很想知道，通过合理操作，他最多可以赢得多少钱。请你帮他计算这个最大值。

输入的第一行包含三个由空格分隔的整数 $m, k, p\ (2 \leq m \leq 10^5;\ 0 \leq k, p \leq 10^9)$。 接下来的 $m-1$ 行，每行包含两个由空格分隔的整数 $a_i, b_i\ (1 \leq a_i, b_i \leq m; a_i \neq b_i)$，表示树上的一条边。 树的结点编号为 $1$ 到 $m$，根结点编号为 $1$。

输出一个整数，即 Mashmokh 可以获得的最大金额。

下图展示了第一个样例中的树结构。黑色、红色、蓝色分别表示结点内水量为 0、1、2 的情况。 实现获得最大金额的方法之一是将 1 升水分别倒入 3 号和 4 号结点。初始状态如下图所示。 第一步，Mashmokh 付出一枚硬币，将 3 号结点的水箱门关闭。此后的树状态如图： 第二步后，根节点内有 2 升水，如下图所示。  由 ChatGPT 5 翻译