计算无向图中节点对的数量，使得 W - L >= K
Count number of pairs of nodes in undirected graph such that W - L >= K
问题：
给定一个包含 N 个节点和 N-1 条边的无向图。所有边的长度都是1。每条边i的权重为Wi。 (0 <= Wi <= 10.000)
图表保证没有任何循环。所以在 2 个节点之间总是有一条（而且只有一条）最短路径。
从图中取一对节点(u,v):
- l是2个节点之间最短路径的长度
- w是2个节点之间最短路径中权值最大的边
给定数字 K，计算图中的 (u, v) 对的数量，使得 w - l >= K
示例：
N = 3, K = 1
Edges:
1 - 2 - 3
1 - 3 - 2
（边描述为：u - v - w）
答案：6。所有可能的对是：(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)
暴力破解（N < 100）：
遍历所有 (u, v) 对，找到 w 和 l 的最短路径。增加答案如果 w - l >= K .
时间复杂度：O(N^3)
P/S:
我已经尝试并成功了蛮力解决方案（N < 100）。但我正在努力寻找 N 高达 100.000
的解决方案
计算 user202729 的提示：
找到质心（移除后留下子树的顶点，每个子树最多有整棵树的一半顶点）。
计算路径包含质心的对 (u, v)。
删除质心并对每个子树递归操作
第 1 步是 O(n)（有标准算法），第 2 步是 O(n log n)，所以主定理给出 O(n log2 n) 整体。
为了实现第 2 步，在质心处生成树根，并针对质心及其每个 children 计算每个深度的后代数。将 O(log n) 时间前缀和的结果放入 Fenwick 树中。
现在，按权重对边进行排序。从最重的边 e 开始，一直到最轻的边，我们计算路径以 e 作为最重边的对。边e连接aparent和achild；设 x 为 child。对于 x 的每个（不正确的，因此包括 x）后代 u，令 ℓ* = w − K 是最大的 ℓ，使得 w − ℓ ≥ K。使用两个前缀和，计算深度为处的其他子树中的顶点 v 的数量大多数 ℓ* − 深度（u）。然后对 Fenwick 树发布更新以从计数中删除 u。
问题：
给定一个包含 N 个节点和 N-1 条边的无向图。所有边的长度都是1。每条边i的权重为Wi。 (0 <= Wi <= 10.000)
图表保证没有任何循环。所以在 2 个节点之间总是有一条（而且只有一条）最短路径。
从图中取一对节点(u,v):
- l是2个节点之间最短路径的长度
- w是2个节点之间最短路径中权值最大的边
给定数字 K，计算图中的 (u, v) 对的数量，使得 w - l >= K
示例：
N = 3, K = 1
Edges:
1 - 2 - 3
1 - 3 - 2
（边描述为：u - v - w）
答案：6。所有可能的对是：(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)
暴力破解（N < 100）：
遍历所有 (u, v) 对，找到 w 和 l 的最短路径。增加答案如果 w - l >= K .
时间复杂度：O(N^3)
P/S: 我已经尝试并成功了蛮力解决方案（N < 100）。但我正在努力寻找 N 高达 100.000
的解决方案计算 user202729 的提示：
找到质心（移除后留下子树的顶点，每个子树最多有整棵树的一半顶点）。
计算路径包含质心的对 (u, v)。
删除质心并对每个子树递归操作
第 1 步是 O(n)（有标准算法），第 2 步是 O(n log n)，所以主定理给出 O(n log2 n) 整体。
为了实现第 2 步，在质心处生成树根，并针对质心及其每个 children 计算每个深度的后代数。将 O(log n) 时间前缀和的结果放入 Fenwick 树中。
现在，按权重对边进行排序。从最重的边 e 开始，一直到最轻的边，我们计算路径以 e 作为最重边的对。边e连接aparent和achild；设 x 为 child。对于 x 的每个（不正确的，因此包括 x）后代 u，令 ℓ* = w − K 是最大的 ℓ，使得 w − ℓ ≥ K。使用两个前缀和，计算深度为处的其他子树中的顶点 v 的数量大多数 ℓ* − 深度（u）。然后对 Fenwick 树发布更新以从计数中删除 u。