P17307 [ICPC 2026 Xi'an I] Zebra Crossing

Yuki 的面前有一条奇怪的斑马线。 这条斑马线可以看作一棵包含 $n$ 个结点的树，第 $i$ 条边连接结点 $u_i$ 与结点 $v_i$，每个结点的颜色为黑色或白色，用一个长度为 $n$ 的 $\texttt{01}$ 串 $s$ 描述： - 若 $s_i = \texttt{0}$，则结点 $i$ 的颜色为黑色。 - 若 $s_i = \texttt{1}$，则结点 $i$ 的颜色为白色。 Yuki 有一个跳跃能力 $k$，表示当她位于结点 $x$ 时，她可以通过一次跳跃，移动到任意一个满足 $\text{dist}(x, y) \le k$ 的结点 $y$ 上。其中，$\text{dist}(x, y)$ 表示结点 $x$ 到结点 $y$ 的简单路径上的边的数量。 接下来，Yuki 会在斑马线上进行 $n-1$ 轮跳跃。在第 $i$ 轮跳跃中，Yuki 初始时位于结点 $1$，她希望通过若干次跳跃恰好移动到结点 $i+1$。同时，Yuki 希望最小化她跳跃后踩到黑色结点的次数。 你需要帮助 Yuki 求出，每一轮跳跃中 Yuki 跳跃后踩到黑色结点的次数的最小值。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行包含两个正整数 $n, k$ $(1 \le n \le 5\cdot10^5,\ 1 \le k \le n)$。 - 第二行包含一个长度为 $n$ 的 $\texttt{01}$ 串 $s$ $(s_i \in \{\texttt0,\texttt1\})$。 - 接下来 $n-1$ 行，第 $i$ 行包含两个正整数 $u_i, v_i$ $(1 \le u_i, v_i \le n,\ u_i \ne v_i)$。 保证所有测试数据中 $n$ 的总和不超过 $5\cdot10^5$。

对于每组测试数据，输出一行，包含 $n-1$ 个整数，第 $i$ 个整数表示第 $i$ 轮跳跃中 Yuki 跳跃后踩到黑色结点的次数的最小值。

对于第 $1$ 组测试数据： - 对于第 $1$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,2$。 - 对于第 $4$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,3,5$。 对于第 $2$ 组测试数据： - 对于第 $4$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,5$。 - 对于第 $7$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,5,8$。 - 对于第 $8$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,4,9$。