Practice · 4 of 5
Cạnh tối đa nhỏ nhất trên đường
CHALLENGE
Difficulty: intermediate+25 XP
**Bài toán.** Đồ thị vô hướng LIÊN THÔNG n đỉnh, m cạnh (u, v, w). q truy vấn (u, v): trên mọi đường đi từ u đến v, xét cạnh có trọng số TỐI ĐA trên đường đó — in giá trị nhỏ nhất có thể đạt được. **Ràng buộc:** 1 ≤ n ≤ 100 000; 1 ≤ m, q ≤ 200 000; 1 ≤ w ≤ 10^9. Đây là truy vấn bottleneck của tính chất Kruskal (bài 7.2): đáp án là cạnh đang xét khi hai đỉnh truy vấn lần ĐẦU nhập chung thành phần.
Press Submit to check your solution.
Back to lesson: Practice: DSU & MST Problem Set