AT_scpc2026_div3_h.Cramming

An exam is approaching! queued_q has $T$ hours left until the exam, and the exam covers $N$ topics. Studying each topic basically takes $A$ hours. queued_q wants to study as many topics as possible while keeping the total study time at most $T$.

Some topics are related to one another. If queued_q has previously studied topics related to the topic to be studied next, that topic becomes easier to study. The relationships between exam topics can be represented as a tree with $N$ vertices and $N-1$ edges. The $i$-th edge of the tree means that topic $u_i$ and topic $v_i$ are directly related to each other. When studying topic $i$, if $k$ topics adjacent to $i$ have already been studied, the actual time required to study topic $i$ is $\max(1, A - B \times k)$. In other words, each additional adjacent topic already studied decreases the study time by $B$, but at least $1$ hour must be spent.

queued_q wants to choose the topics to study and their order appropriately so as to study as many topics as possible. Find the maximum number of topics $K$ that queued_q can study within $T$ hours, the minimum time $M$ required to study $K$ topics, and an order that achieves them.

考试即将到来！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$，以及达成该目标的一种学习顺序。

The input is given from Standard Input in the following format:

$N$ $T$ $A$ $B$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输入从标准输入中按以下格式给出：

$N$ $T$ $A$ $B$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

On the first line, output the maximum number of topics $K$ that queued_q can study and the minimum time $M$ required to study $K$ topics, separated by a space.

On the second line, output an optimal order for studying $K$ topics, separated by spaces. If there are multiple optimal orders, output any one of them. If $K=0$, note that the second line should be empty.

第一行输出 queued_q 最多可以学习的主题数 $K$ 以及学习这 $K$ 个主题所需的最少时间 $M$，两者之间用空格分隔。

第二行输出一个学习这 $K$ 个主题的最优顺序，各主题编号之间用空格分隔。若存在多个最优顺序，输出任意一种即可。若 $K=0$，则第二行应为空行。

表示言語

/ /

Constraints

• $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$
• The given relationships always form a tree.
• All given numbers are integers.

表示语言

/ /

约束条件

• $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$
• 给定的关系始终构成一棵树。
• 所有给定的数均为整数。