在无向无环图中找到两个节点之间的最大权重边
Find maximal weight edge between two nodes in an undirected acyclic graph
我们有一个包含 N 个节点和 N-1 个双向边的图（每个边都有一些权重 w )。
现在我们要回答 q 个查询。每个查询给出两个节点 u 和 v 以及任意边的最大允许成本 x。如果从 u 到 v 之间的所有边的单个边权重小于或等于 x, 然后我们打印 Yes 否则我们打印 No.
约束条件如下：
1 ≤ N,q ≤ 10^6
1 ≤ w,x ≤ 10^9
我已经尝试过暴力解决方案，但它给出了 TLE。我知道我必须做一些预处理，但无法解决。
我在这里发现了一个类似的问题，但没有人清楚地解决了那部分问题。
.
您可以访问 link 以更好地解释问题。
这可以使用 Union Find（也称为 Diesjoint Set Union，如果从未听说过它，您可以在 O(nlog( n) + qlog(q))
读取所有查询并将它们存储在某个数组结构中（保留查询信息 u v x 和查询索引）
按权重对所有查询进行排序
按权重对所有边进行排序
遍历所有查询，如果需要合并所有未合并的边，权重 <= 查询权重
如果节点 u 和 v 在同一个连通分量中 (Find(u)==Find(v)) 那么这个查询的答案是 Yes else no
- 按需要的顺序打印答案
我们有一个包含 N 个节点和 N-1 个双向边的图（每个边都有一些权重 w )。 现在我们要回答 q 个查询。每个查询给出两个节点 u 和 v 以及任意边的最大允许成本 x。如果从 u 到 v 之间的所有边的单个边权重小于或等于 x, 然后我们打印 Yes 否则我们打印 No.
约束条件如下：
1 ≤ N,q ≤ 10^6
1 ≤ w,x ≤ 10^9
我已经尝试过暴力解决方案，但它给出了 TLE。我知道我必须做一些预处理，但无法解决。
我在这里发现了一个类似的问题，但没有人清楚地解决了那部分问题。
您可以访问 link 以更好地解释问题。
这可以使用 Union Find（也称为 Diesjoint Set Union，如果从未听说过它，您可以在 O(nlog( n) + qlog(q))
读取所有查询并将它们存储在某个数组结构中（保留查询信息 u v x 和查询索引）
按权重对所有查询进行排序
按权重对所有边进行排序
遍历所有查询，如果需要合并所有未合并的边，权重 <= 查询权重
如果节点 u 和 v 在同一个连通分量中 (Find(u)==Find(v)) 那么这个查询的答案是 Yes else no
- 按需要的顺序打印答案