题目描述

我们定义一个长度为 $k$ 的序列的绝对众数为：该序列中唯一一个出现次数严格大于 $\lfloor \frac{k}{2} \rfloor$ 的数值。如果不存在这样的数值，则称该序列没有绝对众数。例如，序列 $[1,3,2,3,3]$ 的绝对众数为 $3$（因为 $3$ 出现了 $3$ 次，$3 > \lfloor \frac{5}{2} \rfloor = 2$），而序列 $[1,2,3,4,5]$ 和 $[1,3,2,3,4]$ 则没有绝对众数。

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

对于每个 $i$（$1 \le i \le n$），请判断是否存在一条非平凡的简单路径 $^{\text{†}}$，使得该路径上顶点构成的数值序列的绝对众数为 $i$。

$^{\text{∗}}$ 树指的是一个无环的连通图。

$^{\text{†}}$ 非平凡的简单路径指的是一个顶点序列 $v_1, v_2, \dots, v_m$（其中 $m \ge 2$），满足对于所有 $1 \le i \le m-1$，顶点 $v_i$ 与 $v_{i+1}$ 之间存在一条边，并且所有顶点均互不相同。注意路径至少包含 $2$ 个顶点。

输入格式

每个测试包含多个测试用例。输入的第一行给出测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 5 \cdot 10^5$），表示顶点数。

每个测试用例的第二行包含 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示写在顶点上的整数。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示一条连接顶点 $u_i$ 与 $v_i$ 的边（$1 \le u_i,v_i \le n$ 且 $u_i \neq v_i$）。

题目保证给定的边构成一棵树，并且所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个长度为 $n$ 的二进制字符串 $s$。其中第 $i$ 个字符 $s_i$ 定义如下：

• 如果存在一条非平凡路径，使得该路径上顶点构成的数值序列的绝对众数为 $i$，则 $s_i$ 为 1；
• 否则，$s_i$ 为 0。

样例

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

000
1010
0001
1001001000100

样例说明

• 在第一个测试用例中，没有任何一条非平凡路径能使得 $1$、$2$ 或 $3$ 成为绝对众数，因此输出的二进制字符串为 000。
• 在第二个测试用例中，路径 $1 \rightarrow 2 \rightarrow 4$ 是一条非平凡路径，在该路径上 $3$ 为绝对众数。

来源

Codeforces 2065F，英文题名 Skibidus and Slay。