Description

The town can be modeled as an undirected tree with $n$ nodes and $n-1$ edges. Each edge has a positive integer weight, and there is a household at each node. Let $\operatorname{dis}(u,v)$ denote the sum of edge weights along the unique simple path between nodes $u$ and $v$.

The organizers will select a starting node $u$ and an ending node $v$ (it is required that $u \neq v$). The unique simple path between $u$ and $v$ will be the race course. All residents will watch the race. The household at node $x$ will go to the node $y$ on the path $u \to v$ that is closest to $x$ (i.e., minimizes $\operatorname{dis}(x,y)$; such a node $y$ is unique). The distance $\operatorname{dis}(y,v)$ is defined as the "passion value" of this household, denoted by $f(x, u, v)$.

Let $g(u,v)$ be the average passion value over all households, defined as $g(u,v) = \frac{1}{n}\sum_{x=1}^n f(x,u,v)$. The organizers consider the race "successful" if the condition $g(u,v)\ge \frac{1}{2}\operatorname{dis}(u,v)+k$ is met.

Given a constant $k$, your task is to count the number of ordered pairs $(u, v)$ such that $u \neq v$ and the race from $u$ to $v$ is "successful".

Formal Definition:

Given an undirected tree with $n$ nodes and positive edge weights. Let $\operatorname{dis}(u,v)$ denote the length of the path between $u$ and $v$. Let $y$ be the node on the simple path $u \to v$ that is closest to node $x$. Define $f(x, u, v) = \operatorname{dis}(y, v)$. Define $g(u,v)=\frac{1}{n}\sum_{x=1}^nf(x,u,v)$. Given a constant $k$, count the number of ordered pairs $(u,v)$ such that $u \ne v$ and $g(u,v)\ge \frac{1}{2}\operatorname{dis}(u,v)+k$.

Input Format

This problem contains multiple test cases. The first line contains a positive integer $T$, the number of test cases.

For each test case: The first line contains two integers, $n$ and $k$. The next $n-1$ lines each contain three integers $x, y, v$, representing an edge connecting nodes $x$ and $y$ with weight $v$. It is guaranteed that the input describes a tree.

Output Format

For each test case, output a single integer on one line, representing the answer.

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

Hint

【Data Range】

For all test cases, it is guaranteed that:

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

This problem uses subtasks for scoring. The descriptions of the subtasks are as follows: