AT_scpc2026_div3_h Cramming

#### 表示言語 / / 試験が近づいている！queued\_q には試験まで $ T $ 時間が残されており，試験範囲には $ N $ 個のトピックがある．各トピックを勉強するには，基本的に $ A $ 時間かかる．queued\_q は費やした勉強時間の合計が $ T $ 以下になるようにしながら，できるだけ多くのトピックを勉強したい． 一部のトピックは互いに関連している．これから勉強しようとしているトピックに関連するトピックを以前に勉強していたなら，そのトピックは勉強しやすくなる．試験トピック間の関連関係は， $ N $ 個の頂点と $ N-1 $ 本の辺を持つ木構造で表すことができる．木の $ i $ 番目の辺は，トピック $ u_i $ とトピック $ v_i $ が互いに直接関連していることを意味する．トピック $ i $ を勉強するとき， $ i $ に隣接するトピックのうち，すでに勉強したトピックが $ k $ 個あるなら，トピック $ i $ を勉強するのにかかる実際の時間は $ \max(1, A - B \times k) $ となる．言い換えると，すでに勉強した隣接トピックが $ 1 $ つ増えるたびに勉強時間は $ B $ だけ減少するが，少なくとも $ 1 $ 時間は勉強しなければならない． queued\_q は勉強するトピックとその順序を適切に定め，できるだけ多くのトピックを勉強したい．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} $

$ 1 $ 行目に，queued\_q が勉強できるトピック数の最大値 $ K $ と， $ K $ 個のトピックを勉強するのにかかる最小時間 $ M $ を空白区切りで出力せよ． $ 2 $ 行目に， $ K $ 個のトピックを勉強する最適な順序を空白区切りで出力せよ．最適な順序が複数ある場合は，そのうちどれを出力してもよい．勉強できるトピックが $ 0 $ 個なら， $ 2 $ 行目には何も出力しないことに注意せよ．

### 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 $ - 与えられる関連関係は常に木構造をなす． - 入力される数値はすべて整数である．