시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB40171743.590%

문제

After restaurants all over Croatia closed because of the lockdown, Mr. Malnar was first overwhelmed with sadness. But he soon realized that there was no point in being sad, and he decided that as soon as the restaurants reopen, he will travel around Croatia and treat himself with the best lamb Croatian restaurants can offer.

Mr. Malnar knows about n cities he could visit, that he labeled with integers from 1 through n. Also, he knows about n − 1 two-way roads that connect those cities, in such a way that it is possible to travel between any two cities.

On every road there is a restaurant that serves lamb, and Mr. Malnar knows how many kilograms of lamb he can order in each one.

He will choose two different cities x and y, and travel from x to y via the shortest path, i.e. the path that uses the minimal number of roads. He will stop at exactly one restaurant, the one where he can order the maximum amount of lamb (if there are multiple such restaurants, he will choose any of them), and he will of course eat all the lamb he orders.

Mr. Malnar considers a path of length l on which he eats w kilograms of lamb to be satisfactory if w − l ≥ k. The length of a path is equal to the number of roads that it goes through.

He wonders how many ordered pairs of distinct cities (x, y) there are, such that the shortest path from x to y is satisfactory. He is very busy, so he asks you to calculate the answer for him.

입력

The first line contains integers n and k (1 ≤ n, k ≤ 100 000), the number of cities, and the satisfaction threshold.

Each of the following n−1 lines contains three integers x, y and w (1 ≤ x, y ≤ n, x ≠ y, 1 ≤ w ≤ 100 000), which means that there is a road that connects x and y, and there is a restaurant on that road where Mr. Malnar can order w kilograms of lamb.

출력

Output the number of ordered pairs of distinct cities (x, y), such that the shortest path from x to y is satisfactory.

서브태스크

번호배점제한
115

1 ≤ n ≤ 1000

235

Cities i and i + 1 (1 ≤ i ≤ n − 1) are directly connected.

360

No additional constraints.

예제 입력 1

3 1
1 2 3
1 3 2

예제 출력 1

6

예제 입력 2

4 1
1 2 1
2 3 2
3 4 3

예제 출력 2

6

예제 입력 3

5 2
1 2 2
1 3 3
3 4 2
3 5 4

예제 출력 3

8

힌트

Clarification of the third example:

The pairs are (1, 3), (3, 1), (1, 5), (5, 1), (3, 5), (5, 3), (4, 5) and (5, 4).

채점 및 기타 정보

  • 예제는 채점하지 않는다.