让我们将 $$$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$$$ 占多数。