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.

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} $

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.

### 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.