AT_joig2026final_h スタンプラリー 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$ 从某个城市出发，初始体力为 $D$。 JOI 君在时刻 $t$ 位于城市 $i$ 时，将依次进行如下操作： 1. 首先，如果当前位置上的集章台已经安装好，即 $T_i \leq t$，就可以盖章。 2. 然后，JOI 君可以选择结束集章活动，或前往与当前城市道路相连且尚未到访过的其他城市。仅当还存在未到访的相邻城市且当前体力不少于 $1$ 时，才可以前往其它城市。 3. 若 JOI 君决定移动，则选择一个与当前城市道路相连且尚未到访的城市 $j$，并前往该城市。体力减少 $1$，在时刻 $t+1$ 抵达城市 $j$。 4. 若选择结束集章活动，且之前至少盖过一次章，则认为集章活动成功，可当场领取礼物。否则视为集章失败。 除了城市之间的移动外，其他所有行动花费时间可忽略。注意，JOI 君不能停留在同一个城市。 你作为活动主办方，需要为每个城市准备足够的礼物，但总数量有限，所以希望只在必要的城市准备礼物。然而，你并不知道 JOI 君将从哪个城市出发。因此，你需要对每个 $s$（$1\leq s\leq N$），求出 JOI 君以城市 $s$ 为起点时，哪些城市 $g$（$1\leq g\leq N$）可能会在集章活动成功后领取礼物，即必须准备礼物的城市数。 给定 IOI 国各城市和道路的信息、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. ($5$ 分) $D \leq 1$。 2. ($9$ 分) $N \leq 3000$，且 $(U_j, V_j) = (j, j+1)$（$1\leq j\leq N-1$）。 3. ($17$ 分) $N \leq 3000$。 4. ($17$ 分) $(U_j, V_j) = (j, j + 1)$（$1\leq j\leq N-1$）。 5. ($33$ 分) $D = N-1$，$N \leq 150\,000$。 6. ($19$ 分) 没有额外约束。 --- ## 样例说明 1 以 $s=1$ 为例，JOI 君的行动路线举例如下： - JOI 君在时刻 $0$ 位于城市 $1$。 - 此时城市 $1$ 尚未安装集章台，无法盖章。 - 当前体力为 $2$，可以前往与城市 $1$ 相连唯一未到访的城市 $2$。 - 体力减少 $1$，时刻 $1$ 到达城市 $2$。 - 在时刻 $1$，JOI 君身处城市 $2$。 - 此时城市 $2$ 也尚未安装集章台，无法盖章。 - 体力还有 $1$，可前往城市 $3$。 - 体力再减 $1$，时刻 $2$ 到达城市 $3$。 - 在时刻 $2$，JOI 君身处城市 $3$。 - 此时城市 $3$ 已安装好集章台，可以盖章。 - 在此选择结束集章活动，已至少盖过一次章，成功集章并领取礼物。 因此，从城市 $1$ 出发，有可能在城市 $3$ 结束且成功，所以需要准备礼物。由此推得，从城市 $1$ 出发时需要准备礼物的城市仅为城市 $3$ 和城市 $4$，所以第 $1$ 行输出 $2$。 同理，从城市 $2$ 出发时，需要准备礼物的城市为城市 $3$、城市 $4$ 和城市 $5$，第 $2$ 行输出 $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 翻译