e-olymp
Задачи

Сбалансируй-ка!

Сбалансируй-ка!

Лидеру команды "Отбой" на День Рождения подарили подвешенное бинарное дерево. Однако, ему не понравилось, что дерево было несбалансировано. Теперь он хочет удалить минимальное количество вершин в дереве, чтобы оно стало сбалансированным. Перед тем, как удалить вершину из дерева, он обязан удалить все вершины из её поддерева.

Напомним, что дерево является сбалансированным тогда и только тогда, когда высота его левого и правого поддеревьев отличается на 1 (высота пустого равна нулю, а высота дерева из одной вершины - единице). Корнем дерева является вершина 1.

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

В первой строке входного файла задано целое число n - количество вершин в дереве (1n1111). В следующих n строках заданы по два целых числа lefti и righti - номера левого и правого ребёнка вершины соответственно, или 0, если этого ребёнка не существует.

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

В единственной строке выходного файла выведите одно число - искомое минимальное количество удаляемых вершин.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
6
2 3
0 0
4 5
0 6
0 0
0 0
Выходные данные #1
1