表示言語
/ /分数: 100 点
问题陈述
考试临近了! queued_q 有 T 距考试还剩几个小时,考试涵盖 N 主题。学习每个主题基本上需要 A 小时。 queued_q 希望学习尽可能多的主题,同时保持总学习时间最多 T.
一些主题彼此相关。如果queued_q之前学习过与接下来要研究的主题相关的主题,那么该主题就会变得更容易学习。考试主题之间的关系可以表示为一棵树: N 顶点和 N-1 边缘。的 i树的第一条边意味着该主题 u_i 和主题 v_i 彼此直接相关。学习课题时 i,如果 k 邻近的主题 i 已经学习过,学习题目实际所需时间 i is \max(1, A - B \times k)。换句话说,每增加一个已经学习的相邻主题就会减少学习时间 B,但至少 必须花费 1 小时。
queued_q想要适当地选择要研究的主题及其顺序,以便研究尽可能多的主题。求最大主题数 K queued_q 可以在其中学习 T 小时,最小时间 M 需要学习 K 主题,以及实现这些主题的顺序。
约束
- 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 queued_q可以学习的最短时间 M 需要学习 K 主题,以空格分隔。
在第二行,输出最佳学习顺序 K 主题,以空格分隔。如果存在多个最优阶,则输出其中任意一个。如果 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 点
문제
시험이 다가오고 있다! 동규는 시험까지 남은 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