P7283 [COCI 2020/2021 #4] Janjetina

During the pandemic lockdown, all restaurants in Croatia were closed. Mr. Malnar was very sad about this. But he soon realized there was no need to be so sad, so he decided that after the lockdown ends, he will travel around Croatia and enjoy the tastiest lamb in the best restaurants.

Mr. Malnar will visit $n$ cities, labeled with integers $1$ to $n$. He also found that there are $n-1$ bidirectional roads, each connecting two of the cities. On each road there is a restaurant that serves lamb, and for each restaurant we are given the maximum weight of lamb that can be ordered. He will choose two cities $x$ and $y$, and travel from $x$ to $y$ along a shortest path (i.e., a path that uses the fewest roads). He will stop at exactly one restaurant, namely the one that can provide the largest amount of lamb (if there are multiple such restaurants, he may choose any one), and he will eat all the lamb he orders. If along a path of length $l$ he can eat $w$ kilograms of lamb, and $w-l \ge k$, then Mr. Malnar calls it **satisfying**. The length of a path is equal to the number of roads it uses. Find how many ordered pairs $(x,y)$ make the shortest path from $x$ to $y$ satisfying.

The first line contains integers $n,k$, where $n$ is the number of cities. The next $n-1$ lines each contain three integers $x,y,w$, meaning there is a road connecting cities $x$ and $y$, and on that road there is a restaurant that provides $w$ kilograms of lamb.

Output the number of ordered pairs that satisfy the requirement.

#### Sample 1 Explanation  The ordered pairs that satisfy the requirement are $(1,3),(3,1),(1,5),(5,1),(3,5),(5,3),(4,5),(5,4)$. #### Constraints **This problem uses bundled evaluation.** | Subtask | Points | Constraints and Notes | | :----------: | :----------: | :----------: | | $1$ | $15$ | $1 \le n \le 1000$ | | $2$ | $35$ | City $i$ and city $i+1$ ($1 \le i \le n-1$) are directly connected (i.e., the shortest distance is $1$). | | $3$ | $60$ | None. | For all testdata, $1 \le n,k,w \le 10^5$, $1 \le x,y \le n$, $x \neq y$. #### Notes **The score setting follows the original COCI problem, with a full score of $110$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) _T4 Janjetina_.** Translated by ChatGPT 5