AT_joi2026final_i スタンプラリー 5 (Collecting Stamps 5)

在 JOI-kun 所居住的 IOI 国，有 $N$ 个小镇，从 $1$ 到 $N$ 编号。此外，IOI 国中有 $N-1$ 条道路，从 $1$ 到 $N-1$ 编号。第 $j$ 条道路（$1 \leq j \leq N-1$）连接着两个小镇 $U_j$ 和 $V_j$，并且是双向的。通过这些道路，从任意一个小镇都可以到达其它任意小镇。 现在 IOI 国要举办一次盖章集会活动。每个小镇都会设立一个盖章点。第 $i$ 个小镇的盖章点会在时刻 $T_i$ 被安装好。 JOI-kun 决定参加盖章集会。在时刻 $0$，JOI-kun 从某个小镇出发，并且初始体力为 $D$。 当 JOI-kun 在时刻 $t$ 到达第 $i$ 个小镇时，他会执行以下操作： 1. 首先，如果当前小镇的盖章点已经安装完成（即 $T_i \leq t$），他就可以盖章。 2. 接下来，他可以选择结束盖章集会，或者前往相邻（通过道路直接连通）且尚未拜访过的小镇。只有当他当前体力至少为 $1$ 并且存在尚未访问的相邻小镇时，才能移动。 3. 如果 JOI-kun 选择移动，他可以选择任意一个与当前小镇通过道路相连且尚未拜访的小镇 $j$，前往该处。每移动一次，体力减 $1$，并在 $t+1$ 时刻抵达小镇 $j$。 4. 如果 JOI-kun 选择结束盖章集会，若他至少盖过一次章，则此次集会视为成功，可以在当前位置领取奖励。否则，集会失败。 除小镇之间的移动外，其它时间可视作忽略不计。注意，JOI-kun 不能在同一小镇原地停留。 你作为活动策划人，如果 JOI-kun 集会成功，你需要在相关小镇准备奖励品。但奖励品数量有限，因此你希望准备的奖励数量尽量少。不幸的是，你并不知道 JOI-kun 最先从哪个小镇出发。因此，对于每个 $s$（$1 \leq s \leq N$），你需要计算，如果 JOI-kun 从第 $s$ 个小镇出发，需要在哪些小镇准备奖励品。即你需要统计有多少个 $g$（$1 \leq g \leq N$），使得存在一种路径走法，使 JOI-kun 能成功地在小镇 $g$ 结束集会。 给定 IOI 国的小镇与道路信息、JOI-kun 的体力以及各小镇盖章点的安装时间，请编写程序，对于每个起点小镇，输出需要准备奖励品的小镇数量。

从标准输入读取以下数据。 > $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$ 个小镇出发时，需要准备奖励品的小镇数量。

## 子任务 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 以下展示一个当 $s=1$ 时 JOI-kun 的移动示例： - 在时刻 $0$，JOI-kun 在小镇 $1$，进行如下操作： - 小镇 $1$ 的盖章点尚未安装，因此无法盖章。 - 当前体力为 $2$，可向小镇 $2$（唯一未访问的相邻小镇）移动。 - 体力减 $1$，在时刻 $1$ 抵达小镇 $2$。 - 在时刻 $1$，JOI-kun 在小镇 $2$，进行如下操作： - 小镇 $2$ 的盖章点尚未安装，无法盖章。 - 当前体力为 $1$，可向小镇 $3$ 移动。 - 体力减 $1$，在时刻 $2$ 抵达小镇 $3$。 - 在时刻 $2$，JOI-kun 在小镇 $3$，进行如下操作： - 小镇 $3$ 的盖章点已安装，进行盖章。 - JOI-kun 选择在此处结束活动，由于至少盖过一次章，活动成功并领取奖励。 因此，当 JOI-kun 从小镇 $1$ 出发、在小镇 $3$ 结束时，集会可以成功，需要在小镇 $3$ 准备奖励品。同理，从小镇 $1$ 出发时，仅需在小镇 $3$ 和小镇 $4$ 准备奖励品，所以输出的第一行为 $2$。 当 JOI-kun 从小镇 $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$）。 - 所有小镇之间都连通。 - 输入数据均为整数。 由 ChatGPT 5 翻译