Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1029. Интернет по ЛЭП
Динамическое программирование и запоминающие функцииЗадачи на деревьях
Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание (11F) |
| 25/07/2008 | Лето 2008 - 11 (День системного администратора) (F) |
| 26/07/2013 | Лето 2013-18 (День системного администратора) (F) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
8:12
Позвонили из Отдела Учета, сказали, что не могут подключиться к базе данных отчетов по расходам. Выдал им Стандартный Ответ Сисадмина N12 (Ну-у, у меня же это получается!). Оставил их рычать и брызгать слюной в трубку, пока отключал от ИБПшки свою кофеварку и втыкал обратно их сервер. Предложил им попробоватьеще раз. Ну вот, еще один счастливый клиент
11:00
Обыграл Васю в домино. Вася ушел. Вытряхнул запасные костяшки из рукавов ("Всегда обеспечь резервное питание!"). Звонят юзеры, говорят, что сервер Бухгалтерии недоступен. Вытащил "витую пару" из радиоприемника (гораздо лучший прием, я вам скажу!) и воткнул его обратно в хаб. Предложил юзерам попробовать еще раз. Еще несколько счастливых клиентов!
16:58
Подключил кофеварку к хабу, чтобы посмотреть, что случится. Ничего не случилось. Нуууу… почти ничего.
17:00
Показалась ночная смена. Сказал им, что хаб работает просто замечательно и пожелал им приятных выходных.
Позвонили из Отдела Учета, сказали, что не могут подключиться к базе данных отчетов по расходам. Выдал им Стандартный Ответ Сисадмина N12 (Ну-у, у меня же это получается!). Оставил их рычать и брызгать слюной в трубку, пока отключал от ИБПшки свою кофеварку и втыкал обратно их сервер. Предложил им попробоватьеще раз. Ну вот, еще один счастливый клиент
11:00
Обыграл Васю в домино. Вася ушел. Вытряхнул запасные костяшки из рукавов ("Всегда обеспечь резервное питание!"). Звонят юзеры, говорят, что сервер Бухгалтерии недоступен. Вытащил "витую пару" из радиоприемника (гораздо лучший прием, я вам скажу!) и воткнул его обратно в хаб. Предложил юзерам попробовать еще раз. Еще несколько счастливых клиентов!
16:58
Подключил кофеварку к хабу, чтобы посмотреть, что случится. Ничего не случилось. Нуууу… почти ничего.
17:00
Показалась ночная смена. Сказал им, что хаб работает просто замечательно и пожелал им приятных выходных.
Один из интернет-провайдеров решил опробовать новую технологию – передачу данных по линиям электропередач.
Для этого на подстанциях были установлены `N` ретрансляторов.
Рассмотрим `i`-й ретранслятор и провод от него к другому ретранслятору.
Количество ретрансляторов, сигнал от которых к `i`-му проходит через рассматриваемый провод,
назовем нагрузкой на данный провод для `i`-го ретранслятора.
Максимум из нагрузок на все провода для `i`-го ретранслятора
называется нагрузкой на данный ретранслятор.
Известно, что по проводам электросети сигнал может пройти
от одного ретранслятора к другому единственным образом.
Требуется написать программу, которая по заданной схеме электросети
подсчитает нагрузку на каждый ретранслятор.
Ввод
Во входном файле содержится число `N` – количество ретрансляторов, за которыми
следуют `N\ -\ 1` пар чисел `u_i\ v_i`, означающих,
что `i`-ый провод соединяет ретрансляторы `u_i` и `v_i`.
Вывод
В выходном файле должно содержаться `N` чисел `a_1,\ a_2,\ …,\ a_N`,
где `a_i` – нагрузка на `i`-ый ретранслятор.
Ограничения
`1\ ≤\ N\ ≤\ 100000`.
Пример ввода 1
3 1 2 2 3
Пример вывода 1
2 1 2
Пример ввода 2
4 1 2 1 3 1 4
Пример вывода 2
1 3 3 3
