E. Kia 烤蛋糕

每个测试的时间限制： $6$ 秒
内存限制： $512$ 兆字节

---

题目描述

你有一个长度为 $n$ 的二进制字符串 $s$ 和一棵有 $n$ 个顶点的树 $T$。设 $k$ 是 $s$ 中 $1$ 的个数。我们将按照如下方式构造一个具有 $k$ 个顶点的完全无向加权图：

1. 对于每个满足 $s_i = 1$ 的 $1 \le i \le n$，创建一个标号为 $i$ 的顶点。
2. 对于上一步创建的两个顶点 $u$ 和 $v$，定义它们之间的边权 $w(u,v)$ 为树 $T$ 中顶点 $u$ 和顶点 $v$ 之间的距离$^*$。

一条按顺序访问顶点 $v_1, v_2, \dots, v_m$ 的简单路径$^\dagger$ 被称为nice，如果对于所有 $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} = 1$，否则不会有对应标号的顶点。

对于完全无向加权图中的每个标号为 $i$ 的顶点（即 $1 \le i \le n$ 且 $s_i = 1$），求出从该顶点出发的 nice 简单路径最多能包含多少个顶点。

---

$^*$ 距离：树 $T$ 中两个顶点 $a$ 和 $b$ 之间的距离等于它们之间唯一简单路径上的边数。

$^\dagger$ 路径：顶点序列 $v_1, v_2, \dots, v_m$，满足对于所有 $1 \le i \le m-1$，$v_i$ 和 $v_{i+1}$ 之间有边。简单路径是指没有重复顶点的路径，即对于所有 $1 \le i < j \le m$，有 $v_i \neq v_j$。

---

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例描述如下：

• 第一行包含一个整数 $n$（$1 \le n \le 7 \times 10^4$）—— 二进制字符串 $s$ 的长度以及树 $T$ 的顶点数。
• 第二行包含一个长度为 $n$ 的二进制字符串 $s_1 s_2 \dots s_n$（$s_i \in \{0,1\}$）—— 表示要构建的完全无向加权图中的顶点。
• 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$）—— 树 $T$ 中边的端点。

保证给出的边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $7 \times 10^4$。

---

输出格式

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示从标号为 $i$ 的顶点出发的 nice 简单路径最多能包含的顶点数。如果顶点 $i$ 不存在（即 $s_i = 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$，选中节点标记为黄色。
• 右侧是构造出的完全图。

图中所示的 nice 路径是 $3 \to 4 \to 2$，因为 $w(4,2)=2$ 至少是 $w(3,4)=1$ 的两倍。尝试用 $2 \to 5$ 扩展此路径是不可行的，因为 $w(2,5)=3$ 小于 $2 \cdot w(4,2)=4$。

第二个测试用例：树 $T$ 是一条长度为 $17$ 的简单路径。从节点 $2$ 出发的一个 nice 路径示例是 $2 \to 3 \to 5 \to 9 \to 17$，其边权分别为 $1, 2, 4, 8$，每次翻倍。