无向树中满足最大边权减路径长度≥K的有序节点对计数问题

给定一个包含N个节点、N-1条边的无向图，所有边的长度均为1，每条边i有权重Wi（0 ≤ Wi ≤ 10000）。该图保证无环，因此任意两个节点之间有且仅有一条最短路径。

对于节点对(u, v)，定义如下两个参数：

• l：两点之间最短路径的长度
• w：两点最短路径上所有边的最大权重

给定数值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则计数加1。时间复杂度：O(N³)

采用点分治算法，时间复杂度为O(N log² N)，可稳定处理1e5规模的数据。

核心思路 #

点分治是处理树上路径统计问题的经典算法，核心逻辑如下：

1. 每次选出当前树的重心（删除后所有子树大小不超过原树大小的1/2），统计所有经过重心的合法路径数目
2. 标记重心为已访问，递归处理重心的所有子树，避免重复计数

具体实现步骤 #

步骤1：收集路径属性 #

对于当前重心，遍历所有子树，收集子树中每个节点到重心的两个属性：

• d：节点到重心的路径长度（即边数）
• mx：节点到重心的路径上的最大边权

同时单独统计一端为重心的合法路径：只要满足mx - d ≥ K，就计入临时结果，对应有序对(重心, 节点)和(节点, 重心)。

步骤2：统计跨子树的合法路径 #

我们需要统计两端来自不同子树的合法路径，这类路径必然经过重心：

1. 将所有收集到的(mx, d, 子树编号)按mx从小到大排序
2. 用树状数组维护已遍历节点的d的出现次数，同时按子树编号区分，避免统计同一子树内的路径：
   • 遍历排序后的序列，对于当前第i个节点，所有排在前面的节点的mx都≤当前mx_i，因此路径的最大边权为mx_i，判定条件转化为mx_i - (d_i + d_j) ≥ K → d_j ≤ mx_i - K - d_i
   • 查询树状数组中符合d_j条件的数量，减去当前节点所属子树内已遍历的符合条件的数量，累加到总结果中
   • 将当前节点的d更新到全局树状数组和对应子树的统计结构中

步骤3：递归处理子树 #

完成当前重心的贡献统计后，递归处理每个子树，重复上述步骤即可。

结果转换 #

上述步骤统计的是无序对的数量，最终有序对结果直接乘以2即可。

内容的提问来源于stack exchange，提问作者unglinh279