P15947 [JOI Final 2026] 集邮 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$，JOI 君从其中一座城镇出发。此外，JOI 君在时间 $0$ 拥有耐力值 $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$\ > $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 君从城镇 $s$ 出发时必须准备礼物的城镇数量。

### 样例 1 我们展示一个当 $s = 1$ 时 JOI 君行动的例子。 - 在时间 $0$，JOI 君在城镇 $1$ 并采取以下行动。 - 城镇 $1$ 的盖章站尚未设置，所以 JOI 君没有盖章。 - JOI 君当前的耐力值是 $2$。他移动到城镇 $2$，这是通过道路与城镇 $1$ 相连的未访问城镇之一。 - JOI 君的耐力值减少 $1$，并于时间 $1$ 到达城镇 $2$。 - 在时间 $1$，JOI 君在城镇 $2$ 并采取以下行动。 - 城镇 $2$ 的盖章站尚未设置，所以 JOI 君没有盖章。 - JOI 君当前的耐力值是 $1$。他移动到城镇 $3$，这是通过道路与城镇 $2$ 相连的未访问城镇之一。 - JOI 君的耐力值减少 $1$，并于时间 $2$ 到达城镇 $3$。 - 在时间 $2$，JOI 君在城镇 $3$ 并采取以下行动。 - 城镇 $3$ 的盖章站已经设置，所以 JOI 君盖章。 - JOI 君选择在这里结束盖章拉力赛。由于他已经盖了至少一次章，盖章拉力赛成功。他收到一份礼物。 因此，当 JOI 君从城镇 $1$ 出发并在城镇 $3$ 结束盖章拉力赛时，盖章拉力赛可以成功，因此有必要在城镇 $3$ 准备礼物。当 JOI 君从城镇 $1$ 出发时，仅需在城镇 $3$ 和 $4$ 准备礼物，因此输出的第一行应为 $2$。 此外，当 JOI 君从城镇 $2$ 出发时，仅需在城镇 $3, 4$ 和 $5$ 准备礼物，因此输出的第二行应为 $3$。 该输入样例满足子任务 $3, 6$ 的限制。 ### 样例 2 该输入样例满足子任务 $1, 2, 3, 4, 6$ 的限制。 ### 样例 3 该输入样例满足子任务 $3, 5, 6$ 的限制。 ### 限制 - $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 分) 无额外限制。