← 返回题目列表

AtCoder · scpc2026_div3_h

H. 临时抱佛脚

中文机器翻译题面 查看原题

表示言語

/ /

分数: 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