F. Вулканические извержения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано неориентированное дерево с корнем в вершине $$$1$$$, где каждая вершина имеет вес $$$w_i\in\{1,-1\}$$$.

Вулкан в корне извергается в момент времени $$$0$$$. В момент времени $$$t$$$ лава затопляет все вершины, расстояние до которых от корня составляет не более $$$t$$$, где расстояние — это количество рёбер на кратчайшем пути между двумя вершинами.

В момент времени $$$0$$$ вы находитесь на вершине $$$st$$$ с $$$S$$$ жизнями, изначально $$$S=1$$$. Начиная с момента времени $$$0$$$ (включая момент времени $$$0$$$), в каждый момент времени по порядку происходят следующие события:

  1. Пусть $$$u$$$ — это вершина, в которой вы находитесь в данный момент. Количество ваших жизней увеличивается на $$$w_u$$$, т.е. $$$S\gets S+w_u$$$.
  2. Если $$$S=0$$$ или если вершина $$$u$$$ затоплена лавой в этот момент, вы немедленно умираете.
  3. Вы должны переместиться в соседнюю вершину (включая родителя и потомков; оставаться на месте не разрешается). Вы прибываете в выбранную вершину в следующий момент времени.

Найдите максимальное количество перемещений, которые вы можете сделать, прежде чем умрете.

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

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

Для каждого набора входных данных первая строка содержит два целых числа $$$n,st$$$ ($$$2 \le st \le n \le 5\cdot 10^5$$$), обозначающих количество вершин и вершину, с которой вы начинаете в момент времени $$$0$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$w_i\in\{1,-1\}$$$,$$$w_{st}=1$$$), где $$$w_i$$$ обозначает вес вершины $$$i$$$.

Следующие $$$n-1$$$ строк содержат по два целых числа $$$u,v$$$ ($$$1\le u,v \le n$$$), которые описывают пару вершин, соединённых рёбером.

Гарантируется, что данный граф является деревом, и что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

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

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

Пример
Входные данные
6
7 4
-1 -1 -1 1 1 1 -1
2 1
3 2
4 3
5 4
6 5
7 6
8 2
-1 1 1 1 1 -1 1 1
2 1
6 2
8 6
3 8
7 3
5 7
4 5
8 2
-1 1 -1 -1 -1 1 -1 -1
2 1
8 2
4 1
5 4
3 4
7 2
6 8
8 4
1 1 1 1 1 -1 1 -1
8 1
3 1
4 3
5 4
6 4
7 6
2 5
8 4
1 1 1 1 -1 -1 1 1
2 1
5 1
4 5
8 5
3 8
7 2
6 2
18 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
9 14
14 15
15 16
16 17
17 18
Выходные данные
6
7
3
3
1
13
Примечание

Дерево в первом наборе входных данных:

Первый набор входных данных.

Одна из оптимальных последовательностей перемещений — $$$4\to3\to4\to5\to6\to7\to6$$$, что составляет в общей сложности $$$6$$$ перемещений. Изменения в $$$S$$$ составляют $$$2\to1\to2\to3\to4\to3\to4$$$. Более подробно:

  • В момент времени $$$0$$$ жизней $$$S$$$ становится $$$2$$$, и мы перемещаемся с вершины $$$4$$$ на вершину $$$3$$$.
  • В момент времени $$$1$$$ жизней $$$S$$$ становится $$$1$$$, и мы перемещаемся с вершины $$$3$$$ на вершину $$$4$$$.
  • В момент времени $$$2$$$ жизней $$$S$$$ становится $$$2$$$, и мы перемещаемся с вершины $$$4$$$ на вершину $$$5$$$.
  • В момент времени $$$3$$$ жизней $$$S$$$ становится $$$3$$$, и мы перемещаемся с вершины $$$5$$$ на вершину $$$6$$$.
  • В момент времени $$$4$$$ жизней $$$S$$$ становится $$$4$$$, и мы перемещаемся с вершины $$$6$$$ на вершину $$$7$$$.
  • В момент времени $$$5$$$ жизней $$$S$$$ становится $$$3$$$. Расстояние от вершины $$$7$$$ до корня составляет $$$6$$$, что означает, что вершина $$$7$$$ ещё не затоплена лавой. Мы перемещаемся с вершины $$$7$$$ на вершину $$$6$$$.
  • В момент времени $$$6$$$ жизненная ценность $$$S$$$ становится $$$4$$$, но расстояние от вершины $$$6$$$ до корня составляет $$$5$$$, что означает, что вершина $$$6$$$ затоплена лавой.