题目描述

In front of Yuki is a strange zebra crossing.

This zebra crossing can be viewed as a tree with $n$ nodes. The $i$-th edge connects node $u_i$ and node $v_i$. Each node is colored either black or white, described by a binary string $s$ of length $n$:

• If $s_i = \texttt{0}$, the color of node $i$ is black.
• If $s_i = \texttt{1}$, the color of node $i$ is white.

Yuki has a jumping ability $k$, which means that when she is at node $x$, she can jump to any node $y$ such that $\text{dist}(x, y) \le k$. Here, $\text{dist}(x, y)$ denotes the number of edges on the simple path between node $x$ and node $y$.

Next, Yuki will perform $n-1$ rounds of jumping on the zebra crossing. In the $i$-th round, Yuki starts at node $1$ and wants to reach node $i+1$ through a sequence of jumps. At the same time, Yuki wants to minimize the number of times she lands on a black node after her jumps.

You need to help Yuki find the minimum number of times she lands on a black node for each round of jumping.

输入格式

This problem contains multiple test cases.

The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases.

For each test case:

• The first line contains two positive integers $n, k$ $(1 \le n \le 5\cdot10^5,\ 1 \le k \le n)$.
• The second line contains a binary string $s$ of length $n$ $(s_i \in \{\texttt0, \texttt1\})$.
• The next $n-1$ lines each contain two positive integers $u_i, v_i$ $(1 \le u_i, v_i \le n,\ u_i \ne v_i)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^5$.

输出格式

For each test case, output a single line containing $n-1$ integers, where the $i$-th integer represents the minimum number of times Yuki lands on a black node during the $i$-th round of jumping.

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

提示

For the first test case:

• For the $1$-st round of jumping, one valid sequence of visited nodes is $1, 2$.
• For the $4$-th round of jumping, one valid sequence of visited nodes is $1, 3, 5$.

For the second test case:

• For the $4$-th round of jumping, one valid sequence of visited nodes is $1, 5$.
• For the $7$-th round of jumping, one valid sequence of visited nodes is $1, 5, 8$.
• For the $8$-th round of jumping, one valid sequence of visited nodes is $1, 4, 9$.