← 返回题目列表

AtCoder · joi2026final_i

I. 印章拉力赛 5(收集印章 5)

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

分数: 100 点

问题陈述

有 N JOI君居住的IOI国的城镇,编号为 1 to N。 另外,还有 N-1 IOI 国家的道路,编号为 1 to N-1。 道路 j (1 \leq j \leq N-1) 连接城镇 U_j 和镇 V_j 两个方向。 可以使用一定数量的道路从任何城镇前往任何其他城镇。

现在将在 IOI 国家举办集章活动。 每个城镇将设置一个盖章站。 镇上的邮票站 i (1 \leq i \leq N) 将在某个时间安装 T_i.

JOI君决定参加集章活动。 时 0,JOI君从其中一个城镇出发。 而且JOI君的体力也有 D 时间 0.

当JOI君在城里时 i 时间 t,他采取以下行动。

  1. 首先,如果当前城镇已经安装了印章站,他就按下印章。 也就是说,如果 T_i \leq t.
  2. 接下来,他选择完成集邮活动或搬到另一个城镇。 然而,只有当存在与城镇相连的相邻城镇时,他才能选择搬到另一个城镇 i 经过一条他还没有去过的路,他目前的体力至少是 1.
  3. 如果JOI君选择搬到另一个城镇,他会选择一个未去过的城镇 j 与城镇相连的城镇之间 i 在一条路边,然后移动到那里。 他的体力下降了 1,他到达城镇 j 时间 t+1.
  4. 如果JOI君选择完成印章集会,那么如果他到目前为止至少按下一次印章,则集会成功,并且他可以在那里收到礼物。 否则,集会就不会成功。

假设除了城镇之间的旅行时间之外的所有时间都可以忽略不计。 请注意,JOI 君不能留在同一个城镇。

您是活动组织者。 如果JOI君在集邮活动中成功,你需要在相应的城镇准备礼物。然而,礼物的数量是有限的,所以你要在尽可能少的城镇准备礼物。 不幸的是,你不知道JOI君将从哪个城镇开始。 因此,对于每个 s (1 \leq s \leq N),你想知道JOI君从城镇出发时必须准备礼物的城镇数量 s。 换句话说,您需要计算 g (1 \leq g \leq N)这样,当JOI君在镇上结束时,盖章拉力赛就有可能成功 g.

给定IOI国家的城镇和道路信息、JOI君的体力以及印章站的安装时间,编写一个程序,计算每个城镇, 当JOI君从那个城镇出发时,必须准备礼物的城镇数量。


输入

从标准输入读取以下数据。

N D
T_1 T_2 \cdots T_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}

输出

写 N 行到标准输出。 的 s- 第行 (1\leq s \leq N) 应包含当 JOI-kun 从城镇出发时必须准备礼物的城镇数量 s.


约束

  • 2 \leq N \leq 400\,000.
  • 0 \leq D \leq N-1.
  • 0 \leq T_i \leq N (1 \leq i \leq N).
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq N-1).
  • 可以使用一定数量的道路从任何城镇前往任何其他城镇。
  • 给定值均为整数。

子任务

  1. (3 点) D\leq 1.
  2. (7 点) N\leq 3\,000, (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
  3. (10 点) N\leq 3\,000.
  4. (11 点) (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
  5. (41 点) D=N-1, N \leq 150\,000.
  6. (28 点)没有额外的限制。

样本输入 1

5 2
2 2 0 1 3
1 2
2 3
2 4
4 5

示例输出 1

2
3
4
2
2

我们展示了 JOI 君在 s=1.

  • 时间 0, JOI君在城里 1 并采取以下措施。
    • 镇上的邮票站 1 还没有安装,所以JOI君没有盖章。
    • JOI君目前的体力是 2。他搬到城里 2,这是与城镇相连的未访问城镇之一 1 在一条路边。
    • JOI君的体力减少了 1,他到达城镇 2 时间 1.
  • 时间 1, JOI君在城里 2 并采取以下措施。
    • 镇上的邮票站 2 还没有安装,所以JOI君没有盖章。
    • JOI君目前的体力是 1。他搬到城里 3,这是与城镇相连的未访问城镇之一 2 在一条路边。
    • JOI君的体力减少了 1,他到达城镇 3 时间 2.
  • 时间 2, JOI君在城里 3 并采取以下措施。
    • 镇上的邮票站 3 已经安装好了,所以JOI君按下了印章。
    • JOI君选择在这里结束集章活动。由于他至少盖过一次印章,所以盖章集会成功了。他在那里收到了一份礼物。

因此,当JOI君从城镇出发时 1 并完成镇上的集章活动 3,集章活动可以成功,所以有必要在镇上准备一份礼物 3。 当JOI君从城镇出发时 1,只能在城镇准备礼物 3 和 4,所以输出的第一行应该是 2.

还有,当JOI君从城镇出发时 2,只能在城镇准备礼物 3, 4,和 5,所以输出的第二行应该是 3.

该输入示例满足子任务的约束 3,6.


示例输入 2

5 1
0 1 2 1 2
1 2
2 3
3 4
4 5

示例输出 2

2
1
2
0
1

该输入示例满足子任务的约束 1,2,3,4,6.


示例输入 3

7 6
2 3 0 4 1 3 4
1 2
2 3
2 4
1 5
1 6
6 7

示例输出 3

2
2
7
5
1
2
5

该输入示例满足子任务的约束 3,5,6.