P12499 「DLESS-1」Life Lies in Movement

**A formal definition of the problem is provided at the end of this problem description.** A small town is about to host a marathon race.

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$.

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.

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

#### 【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: | Subtask | $\sum n\le$ | Score | | :----------: | :----------: | :----------: | | $1$ | $500$ | $5$ | | $2$ | $2000$ | $15$ | | $3$ | $5000$ | $20$ | | $4$ | $10^5$ | $20$ | | $5$ | $3\times10^5$ | $20$ | | $6$ | $10^6$ | $20$ |