题目描述
给定一棵有 n 个节点的树,每个节点都有一种颜色。
设定一个整数 k。如果当前位于节点 x,一次移动可以前往任意的满足从 x 到 y 的树上路径的边数不超过 k 的节点 y。
- 即,需要满足 dist(x,y)≤k。
现在进行 n−1 次独立的任务。
对于第 i 次任务,从节点 1 出发,通过若干次移动最终到达节点 i+1。每次移动到一个新节点后,都算作踩到该节点一次。
注意 1 号点并不算在其中。
请你分别计算,对于每个目标节点,从节点 1 出发到达它时,最少需要踩到多少次黑色节点。
输入时,我们用一个长度为 n 的二进制串 s 表示节点颜色:
- si=0 表示节点 i 为黑色;
- si=1 表示节点 i 为白色。
输入格式
输入包含多组测试数据。
第一行包含一个整数 t(1≤t≤105),表示测试数据组数。
对于每组测试数据:
- 第一行包含两个整数 n,k(1≤n≤5×105,1≤k≤n)。
- 第二行包含一个长度为 n 的二进制字符串 s,其中 si 表示节点 i 的颜色。
- 接下来 n−1 行,每行包含两个整数 ui,vi(1≤ui,vi≤n,ui=vi),表示树中的一条无向边。
保证所有测试数据满足:
∑n≤5×105.
输出格式
对于每组测试数据,输出一行包含 n−1 个整数。
第 i 个整数表示从节点 1 出发,通过每次最多跨越 k 条树边的移动到达节点 i+1 时,能够达到的最小黑色节点踩踏次数。
样例 1 输入
2
5 1
01010
2 1
1 3
3 4
3 5
9 3
100010000
1 2
2 3
2 4
3 5
3 6
4 7
6 8
7 9
样例 1 输出
0 1 1 2
1 1 1 0 1 1 1 2
数据范围
对于所有测试数据,保证:∑n≤5⋅105,1≤k≤n,1≤t≤105。
| 测试点 |
n≤ |
t≤ |
特殊性质 |
| 1∼4 |
10 |
无 |
| 5∼8 |
1000 |
105 |
| 9∼10 |
5⋅105 |
k≤1 |
| 11∼13 |
黑色点数量不超过 200 |
| 14∼16 |
树是一条链 |
| 17∼20 |
无 |