Олимпиадный тренинг

Задача . Nearby Cows


Задача

Темы: графы

Фермер Джон заметил, что его коровы часто перемещаются между соседними полями. Теперь он хочет посадить на каждом поле травы столько, чтобы хватало не только корове, изначально расположенной на этом поле, но и для тех коров, которые приходят сюда с соседних полей.
Ферма Джона состоит из N полей (1 <= N <= 100,000), некоторые из которых соединены двунаправленными дорожками (N-1 всего). Между любыми двумя полями I и j имеется уникальный путь по дорожкам. На поле I изначально пасется C(i) коров. Коровы могут переходить на соседние поля, используя не более чем K дорожек (1 <= K <= 20).
Фермер Джон хочет посадить на каждом поле травы столько, чтобы прокормить максимальное количество коров M(i) – это максимальное количество коров, которые потенциально могут перейти на поле I, используя не более чем K дорожек. По заданной структуре фермы и количеству коров C(i) на каждом поле I помогите ФД вычислить M(i) для каждого поля.
PROBLEM NAME: nearcows
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..N:Каждая строка содержит два разделенных пробелом целых числа, I j (1 <= i,j <= N), указывающих, что поля I и j связаны непосредственной дорожкой.
* Строки N+1..2N: Строка N+i содержит целое число C(i). (0 <= C(i) <=1000)
Формат выходных данных
* Строка 1..N: Строка i должна содержать целое значение M(i).
Примечание
Для поля 1 M(1) = 15 коров на расстоянии не более чем 2 дорожки, и т.д.
Примеры
№Входные данныеВыходные данные
1 
6 2
5 1
3 6
2 4
2 1
3 2
1
2
3
4
5
6
 
15
21
16
10
8
11
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет