COCI '20 Contest 4 #4 Janjetina

Points: 20 (partial)

Time limit: 1.5s

Memory limit: 512M

Problem types

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$ ~n~ cities he could visit, that he labeled with integers from $1$ ~1~ through $n$ ~n~. Also, he knows about $n-1$ ~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$ ~x~ and $y$ ~y~, and travel from $x$ ~x~ to $y$ ~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$ ~l~ on which he eats $w$ ~w~ kilograms of lamb to be satisfactory if $w-l \ge k$ ~w-l \ge 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)$ ~(x, y)~ there are, such that the shortest path from $x$ ~x~ to $y$ ~y~ is satisfactory. He is very busy, so he asks you to calculate the answer for him.

Input Specification

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

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

Output Specification

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

Constraints

Subtask	Points	Constraints
$1$ ~1~	$15$ ~15~	$1 \le n \le 1000$ ~1 \le n \le 1000~
$2$ ~2~	$35$ ~35~	Cities $i$ ~i~ and $i+1$ ~i+1~ $(1 \le i \le n-1)$ ~(1 \le i \le n-1)~ are directly connected.
$13$ ~13~	$60$ ~60~	No additional constraints.

Sample Input 1

3 2
1 2 3
1 3 2

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Explanation for Sample 3

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

Comments

There are no comments at the moment.