题目描述

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 跳跃后踩到黑色结点的次数的最小值。

2
5 1
01010
3 5
2 1
1 3
3 4
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9

0 1 1 2
1 1 1 0 1 1 1 2

提示

对于第 $1$ 组测试数据：

• 对于第 $1$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,2$。
• 对于第 $4$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,3,5$。

对于第 $2$ 组测试数据：

• 对于第 $4$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,5$。
• 对于第 $7$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,5,8$。
• 对于第 $8$ 轮跳跃，一种满足要求的方案中经过的点依次为 $1,4,9$。