Задача №113866. Бюрократия
Мирко стал генеральным директором крупной корпорации. В компании работает N человек, пронумерованных от 1 до N , Мирко имеет номер 1 . У всех кроме Мирко есть начальник. Начальник может иметь несколько подчинённых, но не более одного своего начальника.
Когда Мирко получает задание от инвесторов, он передаёт его своему подчинённому с наименьшим номером. Этот подчинённый также передаёт его своему подчинённому с наименьшим номером, и так далее, пока задание не перейдёт несчастливому работнику без подчинённых, который должен сделать задание.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 и так далее. Потом тот, кто на самом деле сделал работу, осознаёт, насколько эта капиталистическая система несправедлива и увольняется с работы.
Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации. Ему стало интересно, сколько всего монет получил каждый бывший сотрудник. Помогите ему с этим.
Первая строка содержит одно натуральное число N ( 1 ≤ N ≤ 2·10 5 ) — число сотрудников компании. Следующая строка содержит N - 1 чисел a 2 , a 3 , ... a n ( 1 ≤ a i < i ), a i — номер начальника i -го сотрудника.
Выведите N чисел, i -е число должно означать, сколько монет получил i -й сотрудник
Программы, верно работающие при 2 ≤ N ≤ 5000 оцениваются в 50 баллов.
Пояснения к первому примеру:
3 1 1
5 1 1
5 1 2 2 4
13 8 1 3 1