Удаление дерева
Автор задачи: Метельский И.С.
Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к IOI (2002-2003). Tree Pascal
URL первоисточника: http://byoi.narod.ru/
Задачу добавил: elena
Успешно сдано решений: 1
Время на тест - 1 с.
Недавно Петя Булочкин выучил новый язык Tree Pascal, использование которого облегчает работу с деревьями. Этот язык позволяет очень просто создавать деревья, организовывать поиск элементов в них и делать множество других полезных вещей. К сожалению, удалять деревья на этом языке уже не так просто. Дело в том, что в Tree Pascal'е отсутствует команда Delete для удаления дерева целиком, присутствует лишь команда CutLeaves для удаления всех сыновей какой-либо вершины при условии, что все ее сыновья являются листьями.
Так как Петя Булочкин - хороший программист, то он стремится к тому, чтобы все его программы работали быстро. Для этого ему нужно, в частности, уметь быстро удалять деревья. Проведенные Петей исследования показали, что скорость работы команды CutLeaves прямо пропорциональна количеству вершин в дереве. Более точно, если дерево состоит из N вершин, то команда CutLeaves выполняется за N единиц времени. Язык Tree Pascal накладывает некоторые ограничения на использование функции CutLeaves, а именно: если CutLeaves была применена к некоторой вершине, находящейся в некотором поддереве, то до полного удаления этого поддерева нельзя применять CutLeaves к вершинам, не находящимся в этом поддереве. Нетрудно видеть, что время, потраченное на удаление всего дерева, зависит от того, в каком порядке к вершинам будет применяться команда CutLeaves.
Определения.
Деревом называются все те и только те объекты, которые могут быть построены по следующим правилам:
1) Вершина является деревом. Это дерево называется простым. В этом дереве его единственная вершина будет корнем и листом. Сыновей у корня в этом дереве нет. Простое дерево содержит только одно поддерево - это оно само. Tree Pascal располагает специальной командой DeletePrimitive для удаления простого дерева за 1 единицу времени.
2) Если A - вершина, а A1, A2, …, Ak - деревья (возможно, простые), то объект, получаемый соединением A с корнями деревьев A1, A2, …, Ak тоже будет деревом. Корнем этого дерева будет вершина A. Множество листьев этого дерева состоит из объединения множества листьев деревьев A1, A2, …, Ak. Сыновьями корня будут корни деревьев A1, A2, …, Ak, сыновья остальных вершин остаются прежними. Множество поддеревьев состоит из объединения множеств поддеревьев для деревьев A1, A2, …, Ak и самого дерева.
На вход будет подаваться дерево X. Разрешается применять к нему следующие две операции:
1) CutLeaves(A) (A - вершина, не являющаяся листом; все сыновья A - листья). Результатом данной операции является новое дерево Y, полученное из X удалением всех сыновей вершины A и ребер, соединяющих их с A. Эта операция работает за N единиц времени, где N - количество вершин в дереве X.
2) DeletePrimitive(X) (X - простое дерево). Результатом применения этой операции является пустое множество; как только она применена к дереву X, оно считается удаленным. Эта операция работает за 1 единицу времени.
Если операция CutLeaves применена к вершине A, а B - любое поддерево дерева X, содержащее вершину A, то до тех пор, пока поддерево B полностью не удалено, запрещается применять CutLeaves к вершинам, не принадлежащим B.
По введенной информации о дереве X найдите минимальное время (в условных единицах), за которое оно может быть удалено.
Формат входного файла input.txt:
Первая строка содержит число N (1<=N<=100000) - количество вершин в дереве (все вершины пронумерованы от 1 до N).
Каждая из следующих N строк содержат описания вершин. Первое число в i-й строке (обозначим его Ci) обозначает количество сыновей у i-й вершины. Следующие Ci чисел - номера сыновей i-й вершины. Номера сыновей всегда больше номера самой вершины. Числа в каждой строке записаны через пробел.
Формат выходного файла output.txt:
Первая строка - одно целое число - минимальное время, необходимое для удаления дерева.
Пример входного файла
12
2 2 3
2 4 5
3 6 7 8
2 9 10
2 11 12
0
0
0
0
0
0
0
Пример выходного файла
37
Ниже нарисовано дерево из примера:
