Worst Bridge on the Way

Difficulty: 2100 6000 ms 128 MB

trees binary-lifting

Answer Q queries on a weighted tree: the maximum edge weight on the path between A and B (0 if A = B).

Input: the first line has N and Q; the next N−1 lines have edges u v w; the next Q lines have the query pairs.

Output: one line per query.

Constraints:

• 2 ≤ N, Q ≤ 10⁵ (tests smaller)
• 1 ≤ w ≤ 10⁶

Sample Tests

4 2
1 2 5
1 3 3
3 4 7
2 4
1 3

7
3

2 1
1 2 9
2 2

0

Read the Editorial