配点 : 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 时,请执行以下操作。
- 首先,如果您所在的城市已经安装了印章站,请按下印章。 也就是说, 如果是T_i \leqq t ,则盖章。
- 接下来,选择是否结束盖章集会或移至另一个城市。 然而,小镇 i 是一个有公路相连的城镇,你还没有去过,你目前的体力是 1 只有这样你才能选择搬到另一个城市。
- 如果JOI选择搬到另一个城市,JOI 有公路连接至您尚未访问过的 i 的城镇 选择 j 并移动它。 体力 1 减少,时间 到达 t+1 倪城 当处于 j 。
- 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).
- 您可以通过多条道路从任何城市前往任何其他城市。 以下是
- 所有输入值都是整数。
小課題
- (5 点) D\leqq 1.
- (9 点) N\leqq 3\,000,(U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1).
- (17 点) N\leqq 3\,000.
- (17 点) (U_j,V_j)=(j,j+1) (1\leqq j \leqq N-1).
- (33 点) D=N-1,N \leqq 150\,000.
- (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 。
- 街 2 尚未安装印章架,因此JOI无法对其进行印章。
- JOI 你现在的体力是多少? 1 。城市 通过公路连接到我尚未访问过的 2 的城市之一。 移至 3 。
- JOI你的体力 1 减少,时间 到达 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 满足约束。