D. Замена MEX на дереве
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с корнем в вершине $$$1$$$ и $$$n$$$ вершинами, а также перестановка $$$p$$$ длины $$$n$$$, состоящая из целых чисел $$$0, 1, \ldots, n - 1$$$, где $$$p_v$$$ обозначает вес вершины $$$v$$$.

Пусть $$$S_v$$$ обозначает множество весов, записанных в вершинах, принадлежащих пути от $$$1$$$ до $$$v$$$. Определим функцию $$$f$$$ как $$$f(v) = \mathrm{MEX}(S_v)$$$, то есть $$$\mathrm{MEX}$$$ множества весов вершин на простом пути между корнем и вершиной $$$v$$$ (включительно), где $$$\operatorname{MEX}$$$ набора целых чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе $$$c$$$.

Также дана следующая операция:

  • Выберите целое число $$$v$$$ ($$$1 \leq v \leq n$$$) и присвойте $$$p_v$$$ значение $$$f(v)$$$.

Ваша цель — найти максимальное значение $$$\sum\limits_{v = 1}^n f(v)$$$ после выполнения вышеописанной операции не более одного раза (возможно, ни разу).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le n - 1$$$) — элементы массива $$$p$$$. Гарантируется, что каждое целое число от $$$0$$$ до $$$n - 1$$$ встречается в $$$p$$$ ровно один раз.

Затем следуют $$$n - 1$$$ строк, каждая из которых содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), обозначающие ребро между вершинами $$$x_i$$$ и $$$y_i$$$. Гарантируется, что эти рёбра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите в одной строке одно целое число: максимальное значение $$$\sum\limits_{v = 1}^n f(v)$$$ после выполнения вышеописанной операции не более одного раза (возможно, ни разу).

Пример
Входные данные
7
1
0
3
1 0 2
1 2
1 3
6
1 4 5 2 0 3
1 4
1 5
6 2
2 5
2 3
5
1 2 3 0 4
1 2
2 3
3 4
4 5
10
9 8 7 1 3 2 5 4 6 0
6 10
3 1
8 7
4 2
2 8
7 5
10 9
3 9
6 4
9
8 4 0 6 5 7 3 1 2
8 3
4 2
4 6
9 3
7 6
1 5
8 5
9 2
7
1 5 2 3 6 0 4
7 6
4 3
7 2
5 1
2 4
6 5
Выходные данные
1
4
12
9
30
26
17
Примечание

В первом примере не выполнять никакой операции — оптимально, поэтому ответ равен $$$1$$$.

Во втором примере имеем

  • $$$f(1) = \mathrm{MEX}(\{p_1\}) = \mathrm{MEX}(\{1\}) = 0$$$
  • $$$f(2) = \mathrm{MEX}(\{p_1, p_2\}) = \mathrm{MEX}(\{1, 0\}) = 2$$$
  • $$$f(3) = \mathrm{MEX}(\{p_1, p_3\}) = \mathrm{MEX}(\{1, 2\}) = 0$$$

И у нас есть следующие варианты:

  1. Ничего не делать, тогда $$$\sum\limits_{v = 1}^n f(v) = 2$$$
  2. Выполнить операцию в вершине $$$1$$$, тогда $$$f(1) = 0$$$ будет присвоено $$$p_1$$$, $$$f(1), f(2), f(3)$$$ изменятся на $$$1$$$, что даёт $$$\sum\limits_{v = 1}^n f(v) = 3$$$
  3. Выполнить операцию в вершине $$$2$$$, тогда $$$f(2) = 2$$$ будет присвоено $$$p_2$$$, $$$f(2)$$$ изменится на $$$0$$$, что даёт $$$\sum\limits_{v = 1}^n f(v) = 0$$$
  4. Выполнить операцию в вершине $$$3$$$, тогда $$$f(3) = 0$$$ будет присвоено $$$p_3$$$, $$$f(3)$$$ изменится на $$$2$$$, что даёт $$$\sum\limits_{v = 1}^n f(v) = 4$$$

Итак, ответ равен $$$4$$$, если выполнить операцию в вершине $$$3$$$.