给定一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和一棵具有 $$$n$$$ 顶点的树 $$$T$$$。设 $$$k$$$ 为 1位于 $$$s$$$ 中。我们将构造一个具有 $$$k$$$ 个顶点的完整无向加权图,如下所示:
- 对于每个 $$$1\le i\le n$$$ 且 $$$s_i = \mathtt{1}$$$,创建一个标记为 $$$i$$$ 的顶点。
- 对于在上述步骤中创建的任意两个标记为 $$$u$$$ 和 $$$v$$$ 的顶点,将它们之间的边权重 $$$w(u, v)$$$ 定义为树 $$$T$$$ 中顶点 $$$u$$$ 和顶点 $$$v$$$ 之间的距离 $$$^{\text{*}}$$$。
A 简单 路径$$$^{\text{†}}$$$ 按此顺序访问标记为 $$$v_1, v_2, \ldots, v_m$$$ 的顶点为 不错 如果对于所有 $$$1\le i\le m - 2$$$,条件 $$$2\cdot w(v_i, v_{i + 1})\le w(v_{i + 1}, v_{i + 2})$$$ 成立。换句话说,路径中每条边的权重必须至少是前一条边权重的两倍。请注意,所有 $$$1\le i\le m$$$ 都必须满足 $$$s_{v_i} = \mathtt{1}$$$,否则,将不存在具有相应标签的顶点。
对于完整无向加权图中标记为 $$$i$$$ 的每个顶点($$$1\le i\le n$$$ 和 $$$s_i = \mathtt{1}$$$),确定从标记为 $$$i$$$ 的顶点开始的任何漂亮简单路径中的最大顶点数。
$$$^{\text{*}}$$$树中两个顶点$$$a$$$和$$$b$$$之间的距离等于顶点$$$a$$$和顶点$$$b$$$之间唯一简单路径上的边数。
$$$^{\text{†}}$$$路径是一系列顶点$$$v_1, v_2, \ldots, v_m$$$,使得对于所有$$$1\le i\le m - 1$$$,$$$v_i$$$ 和 $$$v_{i + 1}$$$ 之间有一条边。简单路径是没有重复顶点的路径,即对于所有$$$1\le i \lt j\le m$$$,$$$v_i\neq v_j$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 7\cdot10^4$$$) - 二进制字符串 $$$s$$$ 的长度和树 $$$T$$$ 中的顶点数。
每个测试用例的第二行包含一个带有 $$$n$$$ 字符的二进制字符串 $$$s_1s_2\ldots s_n$$$ ($$$s_i\in \{\mathtt{0}, \mathtt{1}\}$$$) - 表示要在完整无向加权图中构造的顶点的字符串。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u, v\le n$$$) - 树 $$$T$$$ 的边的端点。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$7\cdot10^4$$$。
输出
对于每个测试用例,输出 $$$n$$$ 个整数,第 $$$i$$$ 个整数表示从标记为 $$$i$$$ 的顶点开始的任何漂亮简单路径中的最大顶点数。如果没有标记为$$$i$$$的顶点,即$$$s_i = \mathtt{0}$$$,则输出$$$-1$$$。
示例
输入复制
35011111 22 33 44 517011010111101011011 22 33 44 55 66 77 88 99 1010 1111 1212 1313 1414 1515 1616 172011 2
输出复制
-1 3 3 3 3 -1 5 4 -1 4 -1 5 5 5 5 -1 4 -1 5 5 -1 3 -1 1
注意
在第一个测试用例中,树$$$T$$$和构建的图如下:
左侧是树$$$T$$$,选定的节点颜色为黄色。右侧是构建的完整图。 图中所示的好路径是$$$3\rightarrow 4\rightarrow 2$$$。该路径很好,因为 $$$w(4, 2) = 2$$$ 至少是 $$$w(3, 4) = 1$$$ 的两倍。使用 $$$2\rightarrow 5$$$ 扩展路径是不可能的,因为 $$$w(2, 5) = 3$$$ 小于 $$$w(4, 2) = 2$$$ 的两倍。
在第二个测试用例中,树 $$$T$$$ 是长度为 $$$17$$$ 的简单路径。从标记为 $$$2$$$ 的顶点开始的良好路径的示例是 $$$2\rightarrow 3\rightarrow 5\rightarrow 9\rightarrow 17$$$,其边权重为 $$$1, 2, 4, 8$$$ 每次加倍。