checking-existence-of-edge-length-limited-paths-ii

< Previous 　　　　　　　　　　　　　　　　 Next >

1724. Checking Existence of Edge Length Limited Paths II (Hard)

Related Topics

[Union Find] [Graph] [Minimum Spanning Tree]

Hints

Hint 1

Find the minimum spanning tree of the given graph.

Hint 2

Root the tree in an arbitrary node and calculate the maximum weight of the edge from each node to the chosen root.

Hint 3

To answer a query, find the lca between the two nodes, and find the maximum weight from each of the query nodes to their lca and compare it to the given limit.