本文介绍一种基于离线处理与并查集（dsu）的高效算法，用于批量回答“路径上最大边权不超过给定阈值”的顶点对（u,v）（u本文介绍一种基于离线处理与并查集（dsu）的高效算法，用于批量回答“路径上最大边权不超过给定阈值”的顶点对（u,v）（u
在带权树中，任意两点间存在唯一简单路径，因此路径上的最大边权是确定的。问题本质等价于：对每个查询阈值 $ q_i $，统计所有满足「u 和 v 在仅保留边权 ≤ $ q_i $ 的边所构成的子图中连通」的无序对 (u, v)（且 u
由于该子图是原树的边诱导子图，它由若干互不相交的树（即森林）组成。若某连通分量大小为 $ s $，则其内部可形成 $ \binom{s}{2} = s(s-1)/2 $ 个合法点对。因此，总答案即为所有连通分量的 $ \binom{s}{2} $ 之和。
核心思路：离线 + 并查集增量构建
- 将所有边按权重升序排序；
- 将所有查询按 $ q_i $ 升序排序，并记录原始索引；
- 使用并查集维护当前已加入（权重 ≤ 当前查询阈值）的边所形成的连通分量；
- 维护全局合法点对总数
total_pairs，每次合并两个大小分别为size[x]和size[y]的连通块时，新增点对数为size[x] * size[y]（因为每个 x 中的点与每个 y 中的点构成新合法对），必须在更新父节点和 size 前计算该乘积。⚠️ 关键修正点（原代码错误）：
在union方法中，若先执行self.size[root_x] += self.size[root_y]再计算乘积，会导致结果偏大。正确顺序应为：# ✅ 正确：先用原始大小相乘，再合并 original_product = self.size[root_x] * self.size[root_y] self.size[root_x] += self.size[root_y] self.parent[root_y] = root_x return original_product以下是完整、通过全部样例的 Python 实现（适配 1-indexed 输入）：
import sys class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return 0 # 确保 rx 是较大分量的根（按秩合并优化） if self.size[rx] <p><strong>注意事项与优化说明：</strong> </p>
- 输入索引处理：题目顶点编号为 1~n，代码统一转为 0-indexed 以匹配数组下标；
- 时间复杂度：排序 $ O(n \log n + m \log m) $，并查集操作近似 $ O((n + m) \alpha(n)) $，整体高效；
- 空间优化：无需存储整棵树结构，仅需边列表与并查集；
- 边界情况：当 $ n = 1 $ 时无点对，输出全 0；当 $ n = 2 $ 且边权 > 所有 $ q_i $，对应查询结果也为 0；
- 可扩展性：该框架可轻松拓展至支持动态加边、带权点对计数等变体问题。
该方法避免了对每组查询单独 DFS/BFS（$ O(mn) $ 不可行），是解决此类“阈值连通性计数”问题的标准范式。
