← 返回题目列表

Codeforces · 2101/E

E. 起亚烤蛋糕

中文机器翻译题面 查看原题

给定一个长度为 $$$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$$$。

示例

输入
复制

3
5
01111
1 2
2 3
3 4
4 5
17
01101011110101101
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
2
01
1 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$$$ 每次加倍。