AdditionalFile5671.zip

#5671. 「JOI 2026 Final Day3」邮戳拉力赛 5

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day3 T3 「スタンプラリー 5 / Collecting Stamps 5」

JOI 君居住的 IOI 国有 $N$ 个城市，编号从 $1$ 到 $N$。此外，IOI 国还有 $N-1$ 条道路，编号从 $1$ 到 $N-1$。第 $j$ 条道路 $(1 \leq j \leq N-1)$ 双向连接城市 $U_j$ 和 $V_j$。在该国，从任意一个城市出发，都可以通过若干条道路到达任何另一个城市。

IOI 国即将举办一场集章拉力赛。每个城市都计划设置一个集章台。城市 $i$ $(1 \leq i \leq N)$ 的集章台将于时刻 $T_i$ 设置完成。

JOI 君决定参加这场集章拉力赛。他将在时刻 $0$ 从任意一个城市开始行动。此外，在时刻 $0$ 时，JOI 君的初始体力为 $D$。

当 JOI 君在时刻 $t$ 位于城市 $i$ 时，他会采取以下行动：

1. 首先，如果当前所在的城市已经设置了集章台，则盖章。也就是说，如果 $T_i \leq t$，则盖一个章。
2. 接下来，选择结束拉力赛或是移动到另一个城市。但是，只有当存在与城市 $i$ 有道路相连且尚未访问过的城市，并且当前的体力不少于 $1$ 时，他才能选择移动到另一个城市。
3. 如果 JOI 君选择移动，他会从与城市 $i$ 有道路连接且尚未访问过的城市中选择一个城市 $j$ 进行移动。此时体力减少 $1$，并于时刻 $t+1$ 到达城市 $j$。
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$。

第二行包含 $N$ 个整数 $T_1,T_2,\cdots ,T_N$

接下来的 $N$ 行，其中第 $i$ 行包含两个整数 $U_i, V_i$。

输出格式

在标准输出中输出 $N$ 行。第 $s$ $(1 \leq s \leq N)$ 行应输出当 JOI 君从城市 $s$ 开始行动时，需要准备奖品的城市数量。

样例 1

输入

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

输出

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$，故第一行输出 $2$。

此外，当 JOI 君从城市 $2$ 开始行动时，需要准备奖品的城市有城市 $3$、城市 $4$ 和城市 $5$，共 $3$ 个，故第二行输出 $3$。

该样例满足子任务 $3, 6$ 的限制。

样例 2

输入

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

输出

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

输出

2
2
7
5
1
2
5

该样例满足子任务 $3, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 400000$。
• $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)$。
• 任意两个城市之间都可以通过若干条道路互相到达。
• 所有输入的数值均为整数。

详细子任务附加限制及分值如下表所示。