Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Khu công nghệ có ~N~ trạm, đánh số từ ~1~ đến ~N~, được nối với nhau bằng ~N - 1~ tuyến cáp hai chiều sao cho giữa hai trạm bất kì luôn có đúng một đường đi (mạng có dạng cây). Tuyến cáp thứ ~i~ nối hai trạm ~u_i, v_i~ và có độ dài ~w_i~.

Ban đầu mọi trạm đều tắt. Thầy Sơn lần lượt thực hiện ~Q~ thao tác, mỗi thao tác cho một trạm ~x~: nếu trạm ~x~ đang tắt thì bật lên, nếu đang bật thì tắt đi.

Sau mỗi thao tác, các trạm đang bật cần trao đổi dữ liệu được với nhau. Thầy Sơn chỉ thuê một số tuyến cáp sao cho chỉ đi trên các tuyến đã thuê vẫn từ trạm đang bật bất kì tới được mọi trạm đang bật khác (được phép đi qua các trạm đang tắt). Hãy cho biết tổng độ dài nhỏ nhất của các tuyến cáp cần thuê. Nếu có không quá một trạm đang bật thì đáp án là ~0~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• ~N - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le w_i \le 10^9)~ mô tả một tuyến cáp.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~x~ ~(1 \le x \le N)~ là trạm được bật/tắt.

Kết quả

Gồm ~Q~ dòng, dòng thứ ~i~ là tổng độ dài nhỏ nhất của các tuyến cáp cần thuê sau thao tác thứ ~i~.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, Q \le 2000~.
• Subtask 2 (~20\%~ số điểm): mỗi tuyến cáp nối hai trạm có số hiệu liên tiếp, tức là ~|u_i - v_i| = 1~ (mạng là một đường thẳng ~1 - 2 - \dots - N~).
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

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

Sample Output 1

0
9
10
10
6
3
3

Giải thích

Sau các thao tác, tập trạm đang bật lần lượt là ~\{2\}~, ~\{2, 4\}~, ~\{2, 4, 5\}~, ~\{1, 2, 4, 5\}~, ~\{1, 2, 5\}~, ~\{1, 5\}~, ~\{1, 3, 5\}~.

• Với ~\{2, 4\}~: thuê các tuyến ~2 - 1~, ~1 - 3~, ~3 - 4~, tổng ~3 + 2 + 4 = 9~.
• Với ~\{2, 4, 5\}~: thuê thêm tuyến ~3 - 5~, tổng ~10~. Bật thêm trạm ~1~ không cần thuê thêm tuyến nào.
• Với ~\{1, 2, 5\}~: các tuyến ~2 - 1~, ~1 - 3~, ~3 - 5~, tổng ~3 + 2 + 1 = 6~.

Nguồn: Đề tự luyện HSG Tin học quốc gia (đề tự soạn).