eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
6
2 3
0 0
4 5
0 6
0 0
0 0
Çıxış verilənləri #1
1