A. Ирис и игра на дереве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ирис есть дерево, корень которого находится в вершине $$$1$$$. Каждая вершина имеет значение $$$\mathtt 0$$$ или $$$\mathtt 1$$$.

Рассмотрим лист дерева (вершина $$$1$$$ никогда не считается листом) и определим его вес. Построим строку, сформированную значениями вершин на пути от корня до этого листа. Тогда вес листа — это разность количества вхождений подстроки $$$\mathtt{10}$$$ и количества вхождений подстроки $$$\mathtt{01}$$$ в этой строке.

Возьмем следующее дерево в качестве примера. Зеленые вершины имеют значение $$$\mathtt 1$$$, в то время как белые вершины имеют значение $$$\mathtt 0$$$.

  • Посчитаем вес листа $$$5$$$: сформированная строка равна $$$\mathtt{10110}$$$. Количество вхождений подстроки $$$\mathtt{10}$$$ равно $$$2$$$, количество вхождений подстроки $$$\mathtt{01}$$$ равно $$$1$$$, так что разность равна $$$2 - 1 = 1$$$.
  • Посчитаем вес листа $$$6$$$: сформированная строка равна $$$\mathtt{101}$$$. Количество вхождений подстроки $$$\mathtt{10}$$$ равно $$$1$$$, количество вхождений подстроки $$$\mathtt{01}$$$ равно $$$1$$$, так что разность равна $$$1 - 1 = 0$$$.

Оценкой дерева назовём количество листьев с ненулевым весом в дереве.

Однако значения некоторых вершин ещё не определены и будут даны вам как $$$\texttt{?}$$$. Заполнение пропусков было бы слишком скучным, поэтому Ирис собирается пригласить Дору поиграть в игру. На каждом ходу одна из девочек выбирает любую из оставшихся вершин со значением $$$\texttt{?}$$$ и изменяет её значение на $$$\mathtt{0}$$$ или $$$\mathtt{1}$$$, при этом Ирис ходит первой. Игра продолжается до тех пор, пока в дереве не останется вершин со значением $$$\mathtt{?}$$$. Ирис стремится максимизировать оценку дерева, в то время как Дора стремится минимизировать её.

Предполагая, что обе девочки играют оптимально, определите итоговую оценку дерева.

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

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

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

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$) — обозначающие ребро между вершинами $$$u$$$ и $$$v$$$.

Гарантируется, что данные рёбра образуют дерево.

Последняя строка содержит строку $$$s$$$ длины $$$n$$$. $$$i$$$-й символ строки $$$s$$$ представляет значение вершины $$$i$$$. Гарантируется, что $$$s$$$ содержит только символы $$$\mathtt{0}$$$, $$$\mathtt{1}$$$ и $$$\mathtt{?}$$$.

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

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

Для каждого набора входных данных выведите одно целое число — итоговую оценку дерева.

Пример
Входные данные
6
4
1 2
1 3
4 1
0101
4
1 2
3 2
2 4
???0
5
1 2
1 3
2 4
2 5
?1?01
6
1 2
2 3
3 4
5 3
3 6
?0????
5
1 2
1 3
1 4
1 5
11?1?
2
2 1
??
Выходные данные
2
1
1
2
1
0
Примечание

В первом наборе входных данных значения во всех вершинах уже определены. Существует три различных пути от корня до листа:

  • От вершины $$$1$$$ до вершины $$$2$$$. Сформированная строка равна $$$\mathtt{01}$$$, так что вес листа равен $$$0-1=-1$$$.
  • От вершины $$$1$$$ до вершины $$$3$$$. Сформированная строка равна $$$\mathtt{00}$$$, так что вес листа равен $$$0-0=0$$$.
  • От вершины $$$1$$$ до вершины $$$4$$$. Сформированная строка равна $$$\mathtt{01}$$$, так что вес листа равен $$$0-1=-1$$$.

Таким образом, есть два листа с ненулевым весом, так что оценка дерева равна $$$2$$$.

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

  • Ирис выбирает изменить значение вершины $$$3$$$ на $$$\mathtt 1$$$.
  • Дора выбирает изменить значение вершины $$$1$$$ на $$$\mathtt 0$$$.
  • Ирис выбирает изменить значение вершины $$$2$$$ на $$$\mathtt 0$$$.

Итоговое дерево выглядит следующим образом:

Единственный лист с ненулевым весом — это $$$3$$$, так что оценка дерева равна $$$1$$$. Обратите внимание, что это может быть не единственная последовательность оптимальных ходов для Ирис и Доры.