Cho cây 𝑇 gồm 𝑛 nút và 𝑄 truy vấn. Các nút của cây được đánh số thứ tự bắt đầu từ 0 và mỗi cạnh của cây được gán một trọng số. Một truy vấn là bộ năm số nguyên {𝑎, 𝑏, 𝑐, 𝑑, 𝑒} đôi một khác nhau. Câu trả lời cho mỗi truy vấn là tổng trọng số nhỏ nhất của cây con chứa năm nút 𝑎, 𝑏, 𝑐, 𝑑, 𝑒.
Yêu cầu: Viết chương trình trả lời 𝑄 truy vấn, với mỗi truy vấn đưa ra tổng trọng số nhỏ nhất của cây con tương ứng.
Dữ liệu:
- Dòng đầu gồm số nguyên dương 𝑛;
- 𝑛 − 1 dòng tiếp theo, mỗi dòng gồm ba số nguyên 𝑢, 𝑣, 𝑤 có nghĩa là nút 𝑢 nối với nút 𝑣 và cạnh (𝑢, 𝑣) có trọng số là 𝑤, dữ liệu luôn đảm bảo 0 ≤ 𝑢, 𝑣 < 𝑛 và 1 ≤ 𝑤 ≤ 1 000;
- Dòng tiếp theo chứa số nguyên dương 𝑄;
- 𝑄 dòng tiếp theo, mỗi dòng gồm năm số nguyên 𝑎, 𝑏, 𝑐, 𝑑, 𝑒.
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Kết quả:
Ghi ra gồm 𝑄 dòng, mỗi dòng là câu trả lời tương ứng cho các truy vẫn trong tệp dữ liệu vào.
Input
6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5
Output
21
16
Ràng buộc:
- 7% số điểm tương ứng với 7% số test có 𝑉 = 5,𝑄 = 1;
- 23% số điểm tương ứng vớ i 23% số test có 5 ≤ 𝑉 ≤ 50 000, 1 ≤ 𝑄 ≤ 10 000 và một nút chỉ nối tối đa với hai nút khác;
- 40% số điểm tương ứng với 40% số test có 5 ≤ V ≤ 50 000, 1 ≤ Q ≤ 100;
- 30% số điểm tương ứng với 30% số test có 5 ≤ 𝑉 ≤ 50 000, 1 ≤ 𝑄 ≤ 10 000.
Nguồn: PREVNOI TEAM 20182019 Hải Phòng