计算无向图中满足 W - L >= K 的节点对数量

Question

问题：

给定一个由 N 个节点和 N-1 个边组成的无向图。所有边的长度均为 1。每条边i 的权重为Wi。（0 <= Wi <= 10.000）

该图保证没有任何循环。因此，两个节点之间始终存在一条（也是唯一的）最短路径。

从图中取出一对节点 (u, v)：

• l是两个节点之间的最短路径的长度
• w是 2 个节点之间的最短路径中权重最大的边

给定数字K ，计算图中满足w - l >= K的 (u, v) 对的数量

例子：

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 的解决方案

Answer 1

要解决 user202729 的提示：

\n

\n

1. 找到质心（删除该顶点留下的子树，每个子树最多拥有整个树一半的顶点）。

   \n
\n

2. 计算路径包含质心的对 (u, v)。

   \n
\n

3. 删除质心并对每个子树进行递归操作。

   \n
\n

\n

步骤 1 的时间复杂度为 O(n)（有一个标准算法），步骤 2 的时间复杂度为 O(n log n)，因此主定理给出的整体时间复杂度为O(n log ^{2 n)。}

\n

要实现步骤 2，请以质心为树根，并为质​​心及其每个子节点计算每个深度的后代数量。将结果放入 Fenwick 树中，以获得 O(log n) 时间前缀和。

\n

现在，按重量对边缘进行排序。从最重的边 e 开始，一直到最轻的边，我们计算路径中以 e 作为最重边的对。边 e 连接父级和子级；让 x 成为孩子。对于 x 的每个（不正确的，因此包括 x）后代 u，令 \xe2\x84\x93* = w \xe2\x88\x92 K 是最大的 \xe2\x84\x93，使得 w \xe2\x88\x92 \ xe2\x84\x93 \xe2\x89\xa5 K. 用两个前缀和，统计深度最多为 \xe2\x84\x93* \xe2\x88\x92 height(u) 的其他子树中顶点 v 的个数。然后向 Fenwick 树发出更新，将 u 从计数中删除。

\n