Codeforces Round 430 (Div. 2) |
---|
Закончено |
Никита играет в новую компьютерную игру. Всего в игре m уровней. На каждом уровне появляется новый класс, который наследуется от класса yi (и yi является родителем нового класса). Таким образом, классы образуют дерево. Изначально существует только один класс с номером 1.
Поменять класс на его соседа в дереве стоит 1 монету, причем обратно класс поменять нельзя. Стоимость смены класса a на класс b равна суммарной стоимости изменений классов на пути от a до b в дереве классов.
Пусть на i-м уровне максимальная стоимость смены одного класса на другой равна x. Выведите для каждого уровня количество классов, для которых существует такой класс y, что смена с этого класса на y стоит x.
Первая строке содержит целое число m — количество запросов(1 ≤ m ≤ 3·105).
Следующие m строк содержат описание уровней. Строка с номером i (1 ≤ i ≤ m) описывает i -ый уровень и содержит одно целое число yi — номер класса, от которого наследуется класс с номером i + 1 (1 ≤ yi ≤ i) .
Пусть на i -ом уровне максимальная стоимость смены одного класса на другой равна x. Выведите для каждого уровня количество классов, для которых существует такой класс y, что смена с этого класса на y стоит x.
4
1
1
2
1
2
2
2
3
4
1
1
2
3
2
2
2
2
Название |
---|