[AdditionalFile3457.zip](file://AdditionalFile3457.zip?type=additional_file)

#3457. 「COCI 2021.1」Janjetina

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

有一棵 $n$ 个点的树，边有边权。

计算满足如下要求的有序点对个数：

• 设 $w$ 为两点之间最短路上边权的最大值，$l$ 为两点之间最短路所经过边的个数，要求 $w-l\ge k$，其中 $k$ 会给定。

输入格式

第一行为两个整数 $n$ 与 $k$。

接下来 $n-1$ 行，每行三个整数 $x,y,w$，表示有一条由 $x$ 到 $y$，边权为 $w$ 的边。

输出格式

输出满足要求的无序点对个数。

样例 1

输入

3 1
1 2 3
1 3 2

输出

6

样例 2

输入

4 1
1 2 1
2 3 2
3 4 3

输出

6

样例 3

输入

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

输出

8

满足条件的点对有 $(1,3),(3,1),(1,5),(5,1),(3,5),(5,3),(4,5),(5,4)$。

数据范围与提示

对于所有子任务，保证 $1\le n,k\le 10^5$，$1\le x,y\le n$，$x\not=y$，$1\le w\le 10^5$。