CF2065F Skibidus and Slay

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.

Each 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 $ .

For 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'.

In 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.