У Ирис есть дерево, корень которого находится в вершине \(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{?}\). Ирис стремится максимизировать оценку дерева, в то время как Дора стремится минимизировать её.
Предполагая, что обе девочки играют оптимально, определите итоговую оценку дерева.
Выходные данные
Для каждого набора входных данных выведите одно целое число — итоговую оценку дерева.
Примечание
В первом наборе входных данных значения во всех вершинах уже определены. Существует три различных пути от корня до листа:
- От вершины \(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\). Обратите внимание, что это может быть не единственная последовательность оптимальных ходов для Ирис и Доры.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|