F. Skibidus and Slaytime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output Let's define the majority of a sequence of $$$k$$$ elements as the unique value that appears strictly more than $$$\left \lfloor {\frac{k}{2}} \right \rfloor$$$ times. If such a value does not exist, then the sequence does not have a majority. For example, the sequence $$$[1,3,2,3,3]$$$ has a majority $$$3$$$ because it appears $$$3 > \left \lfloor {\frac{5}{2}} \right \rfloor = 2$$$ times, but $$$[1,2,3,4,5]$$$ and $$$[1,3,2,3,4]$$$ do not have a majority.Skibidus found a tree$$$^{\text{∗}}$$$ of $$$n$$$ vertices and an array $$$a$$$ of length $$$n$$$. Vertex $$$i$$$ has the value $$$a_i$$$ written on it, where $$$a_i$$$ is an integer in the range $$$[1, n]$$$.For each $$$i$$$ from $$$1$$$ to $$$n$$$, please determine if there exists a non-trivial simple path$$$^{\text{†}}$$$ such that $$$i$$$ is the majority of the sequence of integers written on the vertices that form the path.$$$^{\text{∗}}$$$A tree is a connected graph without cycles. $$$^{\text{†}}$$$A sequence of vertices $$$v_1, v_2, ..., v_m$$$ ($$$m \geq 2$$$) forms a non-trivial simple path if $$$v_i$$$ and $$$v_{i+1}$$$ are connected by an edge for all $$$1 \leq i \leq m - 1$$$ and all $$$v_i$$$ are pairwise distinct. Note that the path must consist of at least $$$2$$$ vertices.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the number of vertices.The second line of each test case contains $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — the integers written on the vertices.Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$, denoting the two vertices connected by an edge ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$).It is guaranteed that the given edges form a tree.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.OutputFor each test case, output a binary string $$$s$$$ of length $$$n$$$ on a separate line. $$$s_i$$$ should be computed as follows: If there is a non-trivial path containing $$$i$$$ as the majority, $$$s_i$$$ is '1'; Otherwise, $$$s_i$$$ is '0'. ExampleInput431 2 31 32 343 1 1 31 22 34 242 4 4 21 22 33 4131 4 4 7 4 7 1 1 7 11 11 11 111 22 33 44 54 62 77 82 96 105 1111 1210 13Output000
1010
0001
1001001000100
NoteIn the first test case, there is no non-trivial path with $$$1$$$, $$$2$$$, or $$$3$$$ as a majority, so the binary string outputted is "000".In the second test case, $$$1\rightarrow 2\rightarrow 4$$$ is a non-trivial path with $$$3$$$ as a majority.