[COCI2020-2021#4] Janjetina
题目背景
疫情封禁期间，克罗地亚的所有餐厅均被关闭。
Malnar 先生为此十分伤感。但他不久发现并没有必要感到如此伤心，因此他决定将在封禁结束后周游克罗地亚，并在最好的餐厅中享用最美味的羊肉。
题目描述
Malnar 先生将访问 $n$ 个城市，分别用整数 $1$ 到 $n$ 表示。同时，他经过调研发现，有 $n-1$ 条连接其中两个城市的双向路。
每条路上均有一家提供羊肉的餐厅，同时给定每个餐厅可以订购的最大羊肉的重量。
他将选择两个城市 $x$ 和 $y$，并以最短路径（指经过的最少的路）从 $x$ 到达 $y$。他将且仅将在一家餐厅停留，且这家餐厅为可提供羊肉重量最多的一家（如果有多家这样的餐厅，他将会选择任意一家），并将订购的羊肉全部吃光。
如果通过一种长度为 $l$ 的路径可以吃到 $w$ 千克的羊肉，且 $w-l \ge k$，那么 Malnar 先生就称之为**满意的**。一种路径的长度等同于其经过路的条数。
求有多少个有序数对 $(x,y)$，使得从 $x$ 到 $y$ 的最短路径是满意的。
输入输出格式
输入格式
第一行输入整数 $n,k$，其中 $n$ 表示城市的个数。
接下来的 $n-1$ 行，每行输入三个整数 $x,y,w$，表示有一条连接城市 $x,y$ 的路，且这条道路有一家提供 $w$ 千克羊肉的餐厅。
输出格式
输出满足题意的有序数对的个数。
输入输出样例
输入样例 #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说明
#### 样例 1 解释
满足题意的有序数对有 $(1,3),(3,1),(1,5),(5,1),(3,5),(5,3),(4,5),(5,4)$。
#### 数据规模与约定
**本题采用捆绑评测。**
| Subtask | 分值 | 数据范围及约定 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ | $1 \le n \le 1000$ |
| $2$ | $35$ | 城市 $i$ 和 $i+1$ （$1 \le i \le n-1$）直接相连（即最短距离为 $1$） |
| $2$ | $60$ | 无 |
对于 $100\%$ 的数据，$1 \le n,k,w \le 10^5$，$1 \le x,y \le n,x \neq y$。
#### 说明
**本题分值按 COCI 原题设置，满分 $110$。**
**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) _T4 Janjetina_。**