P12499 「DLESS-1」Life Lies in Movement

**在本题题目描述最后，我们提供了一份形式化题意**。 一个小镇马上要举行一场马拉松。

这个小镇可以看作一个 $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$。

无

无

#### 【数据范围】 对于所有数据，保证： - $1\le T\le 10^4$ - $1\le n,\sum n\le 10^6$ - $1\le v,k\le10^6$ **本题采用打包测试**，各测试包描述如下： | Subtask | $\sum n\le$ | 分值 | | :----------: | :----------: | :----------: | | $1$ | $500$ | $5$ | | $2$ | $2000$ | $15$ | | $3$ | $5000$ | $20$ | | $4$ | $10^5$ | $20$ | | $5$ | $3\times10^5$ | $20$ | | $6$ | $10^6$ | $20$ |