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