题目背景

在本题题目描述最后，我们提供了一份形式化题意。

一个小镇马上要举行一场马拉松。

题目描述

这个小镇可以看作一个 $n$ 个点，$n-1$ 条边的无向树，每条边有正整数边权，每个点上都有一家住户。记 $\operatorname{dis}(u,v)$ 为 $u$ 到 $v$ 的简单路径的边权和。

主办方将选择一个起点 $u$ 和终点 $v$（需要保证 $u\neq v$），从 $u$ 到 $v$ 的简单路径就是本次比赛的赛道。届时，所有住户都会到赛道上去看比赛，第 $x$ 个点上的住户会到 $u\to v$ 简单路径上满足 $\operatorname{dis}(x,y)$ 最小的 $y$ 去（显然 $y$ 是唯一的），$\operatorname{dis}(y,v)$ 被称作这家住户的“激情值”，记作 $f(x,u,v)$。

设 $g(u,v)$ 表示所有住户的激情的平均值，即 $\frac{1}{n}\sum_{x=1}^nf(x,u,v)$，主办方认为，当 $g(u,v)\ge \frac{1}{2}\operatorname{dis}(u,v)+k$ 时，这场比赛是“成功的”。

现在给出常数 $k$，求有多少有序对 $(u,v)$ 使得比赛是“成功的”。

形式化题意：

给定一棵 $n$ 个点的带边权无向树。

设 $\operatorname{dis}(u,v)$ 表示从 $u$ 到 $v$ 的路径长度，$f(x,u,v)$ 表示 $u\to v$ 简单路径上离 $x$ 最近的一个点到 $v$ 的距离，$g(u,v)=\frac{1}{n}\sum_{x=1}^nf(x,u,v)$。

给定一个常数 $k$，求有多少有序对 $(u,v)$ 使得 $g(u,v)\ge \frac{1}{2}\operatorname{dis}(u,v)+k$。

输入格式

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。

对于每组数据，第一行输入两个数 $n,k$。

接下来 $n-1$ 行，每行三个数 $x,y,v$，代表有一条连结 $x,y$ 的，边权为 $v$ 的边，保证给出的是一棵树。

输出格式

对于每组数据，输出一行一个数字，代表答案。

4
7 3
1 6 3
6 4 1
6 7 4
2 6 2
3 6 1
5 6 2
6 1
2 5 4
2 1 1
2 3 3
2 4 2
6 2 2
10 2
3 2 3
4 9 2
3 10 4
10 4 1
7 6 1
3 5 3
9 8 2
7 10 1
8 1 2
10 1
1 7 2
3 2 3
8 6 4
5 4 2
9 3 2
4 10 3
10 1 4
2 5 3
9 6 2

0
3
2
24

提示

【数据范围】

对于所有数据，保证：

• $1\le T\le 10^4$
• $1\le n,\sum n\le 10^6$
• $1\le v,k\le10^6$

本题采用打包测试，各测试包描述如下：