F. Операции с деревом
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Это многое говорит об обществе.

Однажды черепаха подарила вам дерево с $$$n$$$ вершинами и корнем в вершине $$$x$$$. Вершина $$$i$$$ имеет начальное целое неотрицательное значение $$$a_i$$$.

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

  • Для $$$1 \le i \le n$$$, $$$i$$$-я операция будет выполнена над вершиной $$$i$$$.
  • Для $$$i > n$$$, $$$i$$$-я операция будет выполнена над той же вершиной, что и операция $$$i - n$$$.

Более формально, $$$i$$$-я операция будет выполнена над $$$(((i - 1) \bmod n) + 1)$$$-й вершиной.$$$^{\text{†}}$$$

Обратите внимание, что нельзя пропускать операции; то есть нельзя выполнить $$$i$$$-ю операцию, не выполнив сначала операции $$$1, 2, \ldots, i - 1$$$.

Найдите минимальное количество операций, которое необходимо выполнить, чтобы значения всех вершин стали равны $$$0$$$, при условии, что вы выполняете операции оптимально. Если после конечного числа операций невозможно сделать значения всех вершин равными $$$0$$$, выведите $$$-1$$$.

$$$^{\text{∗}}$$$Поддерево вершины $$$u$$$ — это множество вершин, для которых $$$u$$$ лежит на кратчайшем пути от этой вершины до корня, включая саму $$$u$$$

$$$^{\text{†}}$$$Здесь $$$a \bmod b$$$ обозначает остаток от деления $$$a$$$ на $$$b$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 2000$$$, $$$1 \le x \le n$$$) — количество вершин и корень дерева.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — начальное значение каждой вершины.

В следующих $$$n - 1$$$ строках каждого набора входных данных содержится по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), представляющих собой ненаправленное ребро из $$$u$$$ в $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

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

Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество операций, необходимое для того, чтобы сделать значения всех вершин равными $$$0$$$. Если невозможно сделать значения всех вершин равными $$$0$$$, выведите $$$-1$$$.

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

В первом наборе входных данных вы можете выполнить следующую последовательность операций:

  • На $$$1$$$ операции уменьшите значение вершины $$$1$$$. Эта операция корректна, потому что $$$(((1 - 1) \bmod n) + 1) = 1$$$, и вершина $$$1$$$ находится в поддереве вершины $$$1$$$.
  • На $$$2$$$ операции уменьшите значение вершины $$$2$$$. Эта операция корректна, потому что $$$(((2 - 1) \bmod n) + 1) = 2$$$, и вершина $$$2$$$ находится в поддереве вершины $$$2$$$.
  • На $$$3$$$ операции уменьшите значение вершины $$$2$$$. Эта операция корректна, потому что $$$(((3 - 1) \bmod n) + 1) = 1$$$, а вершина $$$2$$$ находится в поддереве вершины $$$1$$$.