题目描述

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

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

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

输入格式

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

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

输出格式

输出满足要求的无序点对个数。 （但样例输出似乎是按有序给出的，可能题目实际是有序点对，需注意。）

样例 1

输入

text 3 1 1 2 3 1 3 2 输出

text 6

样例 2

输入

text 4 1 1 2 1 2 3 2 3 4 3 输出

text 6

样例 3

输入

text 5 2 1 2 2 1 3 3 3 4 2 3 5 4 输出

text 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$。

子任务 子任务编号 约束 分值 1 $n \le 10^3$ 15/110 2 给定的树为一条链 35/110 3 无特殊限制 60/110