AT_scpc2026_div3_h Cramming

/ / 考试临近！queued\_q 距离考试还有 $T$ 小时，而考试内容涵盖了 $N$ 个知识点。学习每个知识点基本需要 $A$ 小时。queued\_q 希望在总学习时间不超过 $T$ 小时的前提下，尽可能多地学习知识点。 有些知识点彼此关联。如果 queued\_q 之前已经学过与下一个要学的知识点相关联的知识点，那么该知识点会变得更容易学习。考试知识点之间的关系可以用一棵有 $N$ 个结点、$N-1$ 条边的树来表示。第 $i$ 条边意味着知识点 $u_i$ 和知识点 $v_i$ 直接相关。学习第 $i$ 个知识点时，如果它相邻的知识点中已有 $k$ 个被学习过，则学习该知识点实际所需的时间为 $\max(1, A - B \times k)$。也就是说，每多一个相邻且已被学习的知识点，学习时间会减少 $B$，但最少需要 $1$ 小时。 queued\_q 希望合理选择学习的知识点和顺序，使得能学习的知识点数量最多。请你找出能在 $T$ 小时内学习的最多知识点数量 $K$，学习 $K$ 个知识点所需的最短时间 $M$，以及一种能够达到该目标的学习顺序。

输入由标准输入给出，格式如下： > $N\ T\ A\ B\ u_1\ v_1\ u_2\ v_2\ \vdots\ u_{N-1}\ v_{N-1}$

第一行输出 queued\_q 能够学习的最多知识点数量 $K$，和学习 $K$ 个知识点所需的最短时间 $M$，二者之间用空格隔开。 第二行输出一种达到该目标的学习顺序（共 $K$ 个知识点），用空格隔开。如果存在多种最优顺序，输出任意一种。如果 $K=0$，请注意第二行应为空。

### 限制条件 - $1 \leq N \leq 200\,000$ - $0 \leq T \leq 10^9$ - $1 \leq A \leq 10^9$ - $0 \leq B \leq A$ - $1 \leq u_i < v_i \leq N$ - 所给的关系总是形成一棵树。 - 所有输入均为整数。 由 ChatGPT 5 翻译