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

Задача . Running Away From the Barn


Задача

Темы: Деревья Дерево отрезков, RSQ, RMQ

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа pi и li. pi (1 <= pi < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром li (1 <= li <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.
Примеры
№Входные данныеВыходные данные
1 
4 5
1 4
2 3
1 5
 
3
2
1
1
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

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


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

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