← 返回题目列表

Codeforces · 2065/F

F. 斯基比杜斯和斯雷

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

让我们将 $$$k$$$ 元素序列中的大部分定义为严格出现超过 $$$\left \lfloor {\frac{k}{2}} \right \rfloor$$$ 次的唯一值。如果这样的值不存在,则该序列不具有多数。例如,序列 $$$[1,3,2,3,3]$$$ 具有多数 $$$3$$$,因为它出现了 $$$3 > \left \lfloor {\frac{5}{2}} \right \rfloor = 2$$$ 次,但 $$$[1,2,3,4,5]$$$ 和 $$$[1,3,2,3,4]$$$ 没有多数。

Skibidus 找到了一棵有 $$$n$$$ 个顶点的树$$$^{\text{∗}}$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$。顶点 $$$i$$$ 上写有值 $$$a_i$$$,其中 $$$a_i$$$ 是 $$$[1, n]$$$ 范围内的整数。

对于从$$$1$$$到$$$n$$$的每个$$$i$$$,请确定是否存在一个非平凡的简单路径$$$^{\text{†}}$$$,使得$$$i$$$是写在形成路径的顶点上的整数序列的大多数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 顶点数。

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — 写在顶点上的整数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$,表示由边连接的两个顶点 ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$)。

保证给定的边形成一棵树。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上输出长度为 $$$n$$$ 的二进制字符串 $$$s$$$。 $$$s_i$$$ 应按如下方式计算:

- 如果存在包含 $$$i$$$ 为多数的非平凡路径,则 $$$s_i$$$ 为 '1';
- 否则,$$$s_i$$$ 为“0”。

示例

输入 #1

4
3
1 2 3
1 3
2 3
4
3 1 1 3
1 2
2 3
4 2
4
2 4 4 2
1 2
2 3
3 4
13
1 4 4 7 4 7 1 1 7 11 11 11 11
1 2
2 3
3 4
4 5
4 6
2 7
7 8
2 9
6 10
5 11
11 12
10 13

输出 #1

000
1010
0001
1001001000100

注意

在第一个测试用例中,不存在以 $$$1$$$、$$$2$$$ 或 $$$3$$$ 为多数的非平凡路径,因此输出的二进制字符串为“000”。

在第二个测试用例中,$$$1\rightarrow 2\rightarrow 4$$$ 是一条非平凡路径,其中 $$$3$$$ 占多数。