Skip to main content

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.

Back to lesson: Practice: DSU & MST Problem Set