题目大意 给定一棵 $n$ 个节点的树，边带正权。 定义任意两点 $u,v$ 之间的：

$w(u,v)$：路径上的最大边权

$l(u,v)$：路径上的边数

要求统计满足

w ( u , v ) − l ( u , v ) ≥ k w(u,v)−l(u,v)≥k 的无序点对 $(u,v)$ 的数量。

条件转化 我们要数：

max ⁡ e ∈ path ( u , v ) w e − dist edge ( u , v ) ≥ k e∈path(u,v) max ​ w e ​ −dist edge ​ (u,v)≥k 其中 $\text{dist}_{\text{edge}}(u,v)$ 是路径上的边数（不是边权和）。

等价于：

max ⁡ e ∈ path ( u , v ) w e ≥ dist edge ( u , v ) + k e∈path(u,v) max ​ w e ​ ≥dist edge ​ (u,v)+k 思路分析 直接枚举所有点对 $O(n^2)$ 不可行（$n \le 10^5$）。

常见技巧：

考虑按最大边权来统计，比如用并查集从大到小加边（Kruskal 重构树思想）或者点分治。

点分治做法 在点分治时，对于重心 $rt$，考虑经过 $rt$ 的路径 $(u,v)$。

对于 $u \to rt \to v$：

$l(u,v) = d_u + d_v$，其中 $d_u = \text{dist}(u,rt)$（边数）

$w(u,v) = \max(M_u, M_v)$，其中 $M_u$ 是 $u$ 到 $rt$ 路径上的最大边权。

那么条件：

max ⁡ ( M u , M v ) ≥ d u + d v + k max(M u ​ ,M v ​ )≥d u ​ +d v ​ +k 分类讨论： Case 1: $M_u \ge M_v$ 条件：$M_u \ge d_u + d_v + k$ 即 $d_v \le M_u - d_u - k$。

Case 2: $M_v \ge M_u$ 条件：$M_v \ge d_u + d_v + k$ 即 $d_u \le M_v - d_v - k$。

为了避免重复计算 $M_u = M_v$ 的情况，可以严格分成：

$M_u > M_v$ 时用 Case 1

$M_u < M_v$ 时用 Case 2

$M_u = M_v$ 时，按节点编号大小再分。

实现方法 在点分治时，对每个子树，收集所有 $(d_u, M_u)$，然后按 $M_u$ 排序，用 Fenwick 树或排序+双指针统计满足上述不等式的数量。

复杂度：$O(n \log^2 n)$。

针对链的部分分 子任务 2 是链（35分），可以双指针： 固定左端点 $l$，向右找最小的 $r$ 使得 $M(l,r) - (r-l) \ge k$，然后所有 $r' \ge r$ 都满足。 $M(l,r)$ 可以用单调栈 + 稀疏表做，但这里 $l$ 增加时，$M(l,r)$ 会变化，不太好直接双指针？可能需要枚举 $l$，二分 $r$，用 ST 表求区间最大值，$O(n \log n)$。

最终算法选择 正解应是点分治，按上述分类统计，注意去重。

总结 本题核心是树上的路径统计问题，通过点分治将路径按重心分解，利用排序或树状数组高效统计满足 $w - l \ge k$ 的路径数。 主要难点在于分类讨论 $\max(M_u, M_v)$ 的情况，并保证不重不漏。