F. Скибидус и slay
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим мажорирующий элемент последовательности из $$$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]$$$ не имеют мажорирующего элемента.

Скибидус нашел дерево$$$^{\text{∗}}$$$ из $$$n$$$ вершин и массив $$$a$$$ длиной $$$n$$$. Вершина $$$i$$$ имеет значение $$$a_i$$$, написанное на ней, где $$$a_i$$$ — это целое число в диапазоне $$$[1, n]$$$.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ определите, существует ли нетривиальный простой путь$$$^{\text{†}}$$$ такой, что $$$i$$$ является мажорирующим элементом последовательности целых чисел, написанных на вершинах, которые образуют путь.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\text{†}}$$$Последовательность вершин $$$v_1, v_2, ..., v_m$$$ ($$$m \geq 2$$$) образует нетривиальный простой путь, если $$$v_i$$$ и $$$v_{i+1}$$$ соединены ребром для всех $$$1 \leq i \leq m - 1$$$ и все $$$v_i$$$ попарно различны. Обратите внимание, что путь должен состоять как минимум из $$$2$$$ вершин.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого теста выведите двоичную строку $$$s$$$ длиной $$$n$$$ на отдельной строке. $$$s_i$$$ должно вычисляться следующим образом:

  • Если существует нетривиальный путь, содержащий $$$i$$$ как мажорирующий элемент, то $$$s_i$$$ равно '1';
  • В противном случае $$$s_i$$$ равно '0'.
Пример
Входные данные
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
Выходные данные
000
1010
0001
1001001000100
Примечание

В первом примере нет нетривиального пути с $$$1$$$, $$$2$$$ или $$$3$$$ в качестве мажорирующего элемента, поэтому выводимая двоичная строка — «000».

Во втором примере $$$1\rightarrow 2\rightarrow 4$$$ — это нетривиальный путь с $$$3$$$ в качестве мажорирующего элемента.