/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
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.
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.
Input
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}
Output
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.
Sample Input 1
2 1 1 0 1 2
Sample Output 1
1 1 1
Sample Input 2
4 0 1 1 1 2 1 3 1 4
Sample Output 2
0 0
表示言語
/ /Score : 100 points
문제
시험이 다가오고 있다! 동규는 시험까지 남은 T시간 동안 N개의 주제를 공부해야 한다. 각 주제를 공부하는 데에는 A시간이 걸린다. 동규는 시험을 대비하기 위해 소요한 공부 시간의 총합이 T 이하가 되도록 하면서 최대한 많은 주제를 공부하려고 한다.
어떤 주제는 서로 연관되어 있어 이전에 공부했던 주제와 연관된 주제를 공부하면 그 주제를 공부하기가 더 쉬워진다. 시험 주제 간의 연관 관계는 N개의 정점과 N-1개의 간선을 가진 트리 구조로 나타낼 수 있다. 트리의 i번째 간선은 주제 u_i와 주제 v_i가 서로 직접 연관되어 있음을 의미한다. 주제 i를 공부할 때 i와 인접한 주제 중 k개의 주제를 공부했다면 주제 i를 공부하는 데 걸리는 실제 시간은 \max(1, A - Bk)가 된다. 다시 말하면 이미 공부한 연관 주제가 하나 늘어날 때마다 공부 시간이 B만큼 감소하지만 적어도 1시간은 공부해야 한다.
동규는 최적의 순서로 공부하여 시험을 완벽하게 대비하고자 한다. 동규가 T시간 동안 공부할 수 있는 주제 수의 최댓값과 그 방법을 구해 보자.
제한
- 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
- 주어지는 연관 관계는 트리 구조이다.
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N T A B
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
출력
첫째 줄에 동규가 공부할 수 있는 주제 수의 최댓값 K와 K개의 주제를 공부하는 데 걸리는 최소 시간 M을 공백으로 구분하여 출력한다.
둘째 줄에 K개의 주제를 공부하는 최적의 순서를 공백으로 구분하여 출력한다. 만약 가능한 최적의 순서가 여러 가지라면 그중 아무거나 하나를 출력한다. 공부할 수 있는 주제가 0개라면 둘째 줄은 아무것도 출력하지 않음에 유의해야 한다.
입력 예 1
2 1 1 0 1 2
출력 예 1
1 1 1
입력 예 2
4 0 1 1 1 2 1 3 1 4
출력 예 2
0 0
表示言語
/ /配点 : 100 点
問題文
試験が近づいている！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，およびそれらを達成する勉強順序を求めよ．
制約
- 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
- 与えられる関連関係は常に木構造をなす．
- 入力される数値はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
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 行目には何も出力しないことに注意せよ．
入力例 1
2 1 1 0 1 2
出力例 1
1 1 1
入力例 2
4 0 1 1 1 2 1 3 1 4
出力例 2
0 0