Дано взвешенное дерево из n вершин. Каждое ребро имеет неотрицательный вес. Длиной пути между двумя вершинами дерева называется количество ребер в пути. Весом пути называется суммарный вес всех входящих в него ребер.
Две вершины называются близкими, если существует путь между двумя этими вершинами длины не более l и также существует путь между ними веса не более w. Посчитайте количество пар вершин v, u (v < u), таких, что вершины v и u близкие.
В первой строке записаны три целых числа n, l и w (1 ≤ n ≤ 105, 1 ≤ l ≤ n, 0 ≤ w ≤ 109). Далее в n - 1 строках дано описание ребер дерева. В i-той строке записано два целых числа pi, wi (1 ≤ pi < (i + 1), 0 ≤ wi ≤ 104), которые обозначают, что i-ое ребро соединяет вершину (i + 1) и pi и имеет вес wi.
Считайте, что вершины дерева пронумерованы от 1 до n некоторым образом.
Выведите единственное целое число — количество близких пар.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
4 4 6 1 3 1 4 1 3
4
6 2 17 1 3 2 5 2 13 1 6 5 9
9
5000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач