CF2065F.Skibidus and Slay

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

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