← 返回题目列表

AtCoder · joig2026final_h

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

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

配点 : 100 点

問題文

JOI 在您居住的 IOI 国家/地区 有 N 个城市, 它们的编号最大为1 减去 N 。 此外,IOI国家有 N-1 有路, 它们的编号最大为1 减去 N-1 。 路 j (1 \leqq j \leqq N-1) 是一个城市 U_j 和城市 V_j 双向连接。 您可以通过多条道路从任何城市前往任何其他城市。

今后IOI国家将举办集邮活动。 在每个城市 1 将安装两个印章架。 城市 i (1 \leqq i \leqq N) 印台是时间 它安装在 T_i 。

JOI 你决定参加盖章拉力赛。 JOI 你是时候了 从 0 上的任意城市开始您的行动。 还有,JOI君是时候了 当 0 你的体力是 D 。

JOI你是时候了 t 倪城 当处于 i 时,请执行以下操作。

  1. 首先,如果您所在的城市已经安装了印章站,请按下印章。 也就是说, 如果是T_i \leqq t ,则盖章。
  2. 接下来,选择是否结束盖章集会或移至另一个城市。 然而,小镇 i 是一个有公路相连的城镇,你还没有去过,你目前的体力是 1 只有这样你才能选择搬到另一个城市。
  3. 如果JOI选择搬到另一个城市,JOI 有公路连接至您尚未访问过的 i 的城镇 选择 j 并移动它。 体力 1 减少,时间 到达 t+1 倪城 当处于 j 。
  4. JOI 如果您选择结束盖章活动,并且在此之前您已盖过至少一次盖章,则盖章活动将被视为成功,您将当场收到一份礼物。否则,集邮活动就会失败。

假设在城市中移动所需的时间可以忽略不计。 JOI 请注意,你们不能住在同一个城市。

作为锦标赛的组织者,您需要为每个城镇准备礼物,以防 JOI 君在盖章拉力赛中取得成功,但由于礼物数量有限,您希望为所需的最少数量的城镇准备礼物。 但是,您不知道 JOI 将从哪个城市开始。 所以你可以 s (1 \leqq s \leqq N) 关于 JOI Kimiga Town 当你从 s 开始行动时,你需要准备礼物的城镇数量,即JOI君所在的城镇数量 如果您以 g 结束印章拉力赛,则印章拉力赛有可能成功。 我想找到 g (1\leqq g\leqq N的号码。

鉴于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\leqq s \leqq N) 有 JOI 输出从 s 开始行动时需要准备礼物的城镇数量。


制約

  • 2 \leqq N \leqq 400\,000.
  • 0 \leqq D \leqq N-1.
  • 0 \leqq T_i \leqq N (1 \leqq i \leqq N).
  • 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq N-1).
  • 您可以通过多条道路从任何城市前往任何其他城市。 以下是
  • 所有输入值都是整数。

小課題

  1. (5 点) D\leqq 1.
  2. (9 点) N\leqq 3\,000,(U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1).
  3. (17 点) N\leqq 3\,000.
  4. (17 点) (U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1).
  5. (33 点) D=N-1,N \leqq 150\,000.
  6. (19 点)没有额外的限制。

入力例 1

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

出力例 1

2
3
4
2
2

s=1 时 JOI 行为的示例。 在

  • JOI你是时候了 0 倪城 当处于 1 中执行以下操作。
    • 街 1 尚未安装印章架,因此JOI无法对其进行印章。
    • JOI 你现在的体力是多少? 2 。城市 通过公路连接到我尚未访问过的 1 的城市之一。 移至 2 。
    • JOI你的体力 1 减少,时间 到达 1 倪城 当处于 2 。
  • JOI你是时候了 1 倪城 当处于 2 中执行以下操作。
    • 街 2 尚未安装印章架,因此JOI无法对其进行印章。
    • JOI 你现在的体力是多少? 1 。城市 通过公路连接到我尚未访问过的 2 的城市之一。 移至 3 。
    • JOI你的体力 1 减少,时间 到达 2 倪城 当处于 3 。
  • JOI你是时候了 2 倪城 当处于 3 中执行以下操作。
    • 街 3 已经安装了盖章架,JOI可以盖章。
    • JOI 您选择在这里结束盖章拉力赛。集邮活动取得了成功,因为到目前为止,邮票至少已被盖过一次。现场领取礼物。

所以,JOI你就是小镇 从 1 开始你的行动并在城市中移动。 当印章比赛以 3 结束时,印章比赛就有可能成功。 您需要为 3 准备一份礼物。 JOI你就是这座城市 1 开始行动时需要准备礼物的城镇是城镇。 由于只有 3 和城市 4 ,1 在线 2 。 你只需要砍掉

还有,JOI君之镇 2 开始行动时需要准备礼物的城镇是城镇。 由于只有 3,街 4 和城市 5 ,2 在线 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 满足约束。