#P18091. Zebra Crossing

Zebra Crossing

Zebra Crossing

题目描述

给定一棵有 nn 个结点的树,编号为 1,…,n1,\ldots,n。长度为 nn 的二进制串 ss 描述结点颜色:si=0s_i=0 表示黑色,si=1s_i=1 表示白色。

你有跳跃能力 kk。在结点 xx 时,可以跳到任意满足 dist⁡(x,y)≤k\operatorname{dist}(x,y)\le k 的结点 yy,其中距离是两点间简单路径的边数。跳跃途中经过的结点不算落点。

对每个目标结点 i=2,3,…,ni=2,3,\ldots,n,独立地从结点 11 出发,经过若干次跳跃到达 ii,求跳跃后落在黑色结点上的次数最少是多少。

起点的颜色不产生初始费用;若最终落点是黑色,则这次落地也要计数。可以绕行,也可以多次经过同一结点。

输入格式

第一行一个整数 tt。每组第一行两个整数 n,kn,k,第二行一个长度为 nn 的二进制串 ss,接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i 表示一条无向边。

1≤t≤1051\le t\le10^5,1≤n≤5⋅1051\le n\le5\cdot10^5,1≤k≤n1\le k\le n,1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i。输入图为树;所有组的 nn 之和不超过 5⋅1055\cdot10^5。

输出格式

每组输出一行 n−1n-1 个整数,依次为到结点 2,3,…,n2,3,\ldots,n 的答案。当 n=1n=1 时,该组输出空行。

样例输入

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