#CW8. 黑白跳跃(jump)

    ID: 234 传统题 1000ms 512MiB 尝试: 5 已通过: 1 难度: 7 上传者: 标签>成外联盟2026树结构树的分治图结构最短路

黑白跳跃(jump)

题目描述

给定一棵有 nn 个节点的树,每个节点都有一种颜色。

设定一个整数 kk。如果当前位于节点 xx,一次移动可以前往任意的满足从 xx 到 yy 的树上路径的边数不超过 kk 的节点 yy。

  • 即,需要满足 dist⁡(x,y)≤k\operatorname{dist}(x, y) \le k。

现在进行 n−1n - 1 次独立的任务。

对于第 ii 次任务,从节点 11 出发,通过若干次移动最终到达节点 i+1i + 1。每次移动到一个新节点后,都算作踩到该节点一次。

注意 11 号点并不算在其中。

请你分别计算,对于每个目标节点,从节点 11 出发到达它时,最少需要踩到多少次黑色节点。

输入时,我们用一个长度为 nn 的二进制串 ss 表示节点颜色:

  • si=0s_i = 0 表示节点 ii 为黑色;
  • si=1s_i = 1 表示节点 ii 为白色。

输入格式

输入包含多组测试数据。

第一行包含一个整数 tt(1≤t≤1051 \le t \le 10^5),表示测试数据组数。

对于每组测试数据:

  • 第一行包含两个整数 n,kn, k(1≤n≤5×1051 \le n \le 5 \times 10^5,1≤k≤n1 \le k \le n)。
  • 第二行包含一个长度为 nn 的二进制字符串 ss,其中 sis_i 表示节点 ii 的颜色。
  • 接下来 n−1n - 1 行,每行包含两个整数 ui,viu_i, v_i(1≤ui,vi≤n1 \le u_i, v_i \le n,ui≠viu_i \ne v_i),表示树中的一条无向边。

保证所有测试数据满足:

∑n≤5×105.\sum n \le 5 \times 10^5.

输出格式

对于每组测试数据,输出一行包含 n−1n - 1 个整数。

第 ii 个整数表示从节点 11 出发,通过每次最多跨越 kk 条树边的移动到达节点 i+1i + 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\sum n \le 5 \cdot 10^5,1≤k≤n1 \le k \le n,1≤t≤1051 \le t \le 10^5。

测试点 n≤n \le t≤t \le 特殊性质
1∼41 \sim 4 1010 无
5∼85 \sim 8 10001000 10510^5
9∼109 \sim 10 5⋅1055 \cdot 10^5 k≤1k \le 1
11∼1311 \sim 13 黑色点数量不超过 200200
14∼1614 \sim 16 树是一条链
17∼2017 \sim 20 无