Weakest Bridge On Path Problem

Weakest Bridge On Path Problem — ExecCode Hard DSA Practice

Solve the Weakest Bridge On Path problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each road has a weight limit. A truck going from u to v is limited by the weakest road on the unique path. Heavy-light plus a segment tree (or a Kruskal reconstruction tree plus LCA) answers the minimum edge weight on a path. Edges are [u, v, weight]. Each query [u, v] returns that minimum weight. If u = v return 0. If they are disconnected return -1. You are given: n — nodes edges — weighted tree edges queries — pairs [u, v] Return one minimum edge weight per query. The minimum is over edges, so a single-node path has no edge and returns 0.

Examples

Input {'n': 4, 'edges': [[0, 1, 5], [0, 2, 3], [2, 3, 8]], 'queries': [[1, 3], [0, 0], [2, 3]]}; Output [3, 0, 8]. Input {'n': 2, 'edges': [[0, 1, 4]], 'queries': [[0, 1]]}; Output [4]. Input {'n': 3, 'edges': [[0, 1, 2], [0, 2, 9]], 'queries': [[1, 2]]}; Output [2]

Constraints

Tree except disconnected tests return -1 u may equal v

Practice Weakest Bridge On Path free on ExecCode. Browse DSA problems, topic map, and placement guides.