Tổ Tiên Chung Gần Nhất (LCA) và Truy Vấn Min/Max Trọng Số Cạnh Trên Cây
Cho một cây có trọng số gồm N đỉnh (đánh số từ 1 đến N, gốc là đỉnh 1) và N - 1 cạnh có trọng số nguyên.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Binary Lifting LCA, Sparse Table on Tree.
Nội dung đề bài
Mô tả bài toán
Cho một cây có trọng số gồm N đỉnh (đánh số từ 1 đến N, gốc là đỉnh 1) và N - 1 cạnh có trọng số nguyên.
Có Q truy vấn, mỗi truy vấn gồm hai đỉnh u và v. Với mỗi truy vấn, hãy tìm trọng số cạnh lớn nhất nằm trên đường đi đơn nối giữa đỉnh u và đỉnh v trên cây. Nếu u = v, in ra 0.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu chứa số nguyên N (1 ≤ N ≤ 105).
- N - 1 dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w (1 ≤ u, v ≤ N, 0 ≤ w ≤ 109) biểu diễn một cạnh có trọng số.
- Dòng tiếp theo chứa số nguyên Q (1 ≤ Q ≤ 105).
- Q dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N).
Output
- Với mỗi truy vấn, in ra trọng số cạnh lớn nhất trên đường đi giữa u và v trên một dòng.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
5
1 2 4
1 3 2
2 4 5
2 5 1
3
4 5
4 3
1 1Output
5
5
0Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.