Skibidus and Slay
Contest: Codeforces Round 1003 (Div. 4)
Difficulty rating: 1700
Tags: data structures, dfs and similar, graphs, greedy, trees

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.

Input format:
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$$$.

Output format:
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'.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
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

Example output:
000
1010
0001
1001001000100

Editorial:
You can solve this problem using the Auxiliary Tree technique. Formally, the auxiliary tree of $$$k$$$ specified vertices is the tree consisting of the specified vertices and their pairwise lowest common ancestors. It can be shown that such a tree will always have $$$\mathcal{O}(k)$$$ vertices and can be found in $$$\mathcal{O}(k \log n)$$$ time using widely known algorithms.
Observe the fact that, when you transform the value $$$x$$$ into $$$1$$$ and all other values into $$$-1$$$, $$$x$$$ is the majority of the sequence if and only if the transformed sequence has a positive sum. This hints us towards finding the maximum sum of any non-trivial path under the transformed tree. If the maximum sum is found to be positive, then we can determine that there exists a path with $$$x$$$ as its majority.
This subproblem can be solved by running a modified version of Kadane's algorithm, adapted for use on a tree. This adaptation is widely known for the case when the given tree is a binary tree, and it is trivial to modify it for use on any tree while keeping the time complexity to be $$$\mathcal{O}(n)$$$.
The only problem is that solving this for all values is $$$\mathcal{O}(n^2)$$$, so we compress the tree for each value using the Auxiliary Tree technique. By getting the auxiliary tree for the specified vertices, you get the specified vertices and their LCAs. If some vertex is specified, the value on it is transformed into $$$1$$$. Otherwise, the value on it is transformed into $$$-1$$$. Meanwhile, now there are lengths on edges, and an edge with length greater than $$$1$$$ means that there are unspecified vertices compressed in the edge. Therefore, if an edge has length $$$l$$$ which is greater than $$$1$$$, make sure to make a new vertex with value $$$-l+1$$$ in the middle of the edge as it means that $$$l-1$$$ vertices are compressed into the edge.
As there are $$$n$$$ specified vertices in total, finding each auxiliary tree takes $$$\mathcal{O}(n \log n)$$$ time. Solving the rest of the problem for each $$$i$$$ only takes $$$\mathcal{O}(n)$$$ time trivially. Thus, the problem has been solved in $$$\mathcal{O}(n \log n)$$$ time.