algorithm - 在无向无环图中找到两个节点之间的最大权重边

Question

我们有一个包含 N 个节点和 N-1 个双向边的图(每条边都有一些权重 w)。现在我们必须回答 q 个查询。每个查询给出两个节点 u 和 v 以及任意边 x 的最大允许成本。如果从 u 到 v 的路径之间的所有边的单个边权重小于或等于 x，那么我们打印 Yes 否则我们打印No。

约束条件如下:
1 ≤ N,q ≤ 10^6
1 ≤ w,x ≤ 10^9

我已经尝试过蛮力解决方案，但它给出了 TLE。我知道我必须做一些预处理，但无法解决。我在这里发现了一个类似的问题，但没有人清楚地解决了那部分问题。
Maximum edge weight from one node A to node B .
您可以访问该链接以更好地解释问题。

Answer 1

这可以使用 Union Find(也称为 Diesjoint Set Union，如果从未听说过它，您可以查找实现 here)数据结构轻松解决，复杂度为 O(nlog(n) + qlog(q))

1. 读取所有查询并将它们存储在某个数组结构中(保留查询信息 u v x 和查询索引)

2. 按权重对所有查询排序

3. 按权重对所有边进行排序

4. 遍历所有查询，如果需要合并所有未合并的边，权重 <= 查询权重

5. 如果节点 u 和 v 在同一个连通分量 (Find(u)==Find(v)) 中，则此查询的答案是 Yes else no

6. 按需要的顺序打印答案