Problem Background

During the pandemic lockdown, all restaurants in Croatia were closed.

Mr. Malnar was very sad about this. However, he soon realized that there was no need to be so upset, so he decided to tour Croatia after the lockdown and enjoy the most delicious lamb at the best restaurants.

Problem Description

Mr. Malnar will visit \( n \) cities, denoted by integers from 1 to \( n \). He has also discovered that there are \( n-1 \) bidirectional roads connecting pairs of these cities.

Each road has a restaurant that serves lamb, and the maximum weight of lamb that each restaurant can order is given.

He will choose two cities \( x \) and \( y \) and travel from \( x \) to \( y \) via the shortest path (the path with the fewest roads). He will stop at only one restaurant, which is the one that can provide the most lamb (if there are multiple such restaurants, he will choose any one of them), and he will eat all the lamb ordered.

If a path of length \( l \) allows him to eat \( w \) kilograms of lamb, and \( w - l \geq k \), then Mr. Malnar calls this path satisfying. The length of a path is equivalent to the number of roads it traverses.

Determine how many ordered pairs \((x, y)\) exist such that the shortest path from \( x \) to \( y \) is satisfying.

Input Format

The first line contains two integers \( n \) and \( k \), where \( n \) is the number of cities.

The next \( n-1 \) lines each contain three integers \( x \), \( y \), and \( w \), indicating that there is a road connecting cities \( x \) and \( y \) with a restaurant that can provide \( w \) kilograms of lamb.

Output Format

Output the number of ordered pairs that satisfy the conditions.

Sample Input and Output

Sample Input #1

3 1
1 2 3
1 3 2

Sample Output #1

6

Sample Input #2

4 1
1 2 1
2 3 2
3 4 3

Sample Output #2

6

Sample Input #3

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

Sample Output #3

8

Notes

Sample 1 Explanation

The satisfying ordered pairs are \((1, 3), (3, 1), (1, 5), (5, 1), (3, 5), (5, 3), (4, 5), (5, 4)\).

Data Range and Constraints

This problem is evaluated in a bundled manner.

For 100% of the data, \( 1 \le n, k, w \le 10^5 \), \( 1 \le x, y \le n \), \( x \neq y \).

Notes

The points are set according to the original COCI problem, with a maximum of 110 points.

The problem is translated from COCI2020-2021 CONTEST #4 T4 Janjetina.

见题面 Input 部分

见题面 Output 部分