P17307 [ICPC 2026 Xi'an I] Zebra Crossing

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.

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$.