Cập nhật cây khung nhỏ nhất
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây khung nhỏ nhất ban đầu gồm $N$ đỉnh và $N - 1$ cạnh có trọng số. Có $Q$ truy vấn độc lập: mỗi truy vấn đề xuất thêm một cạnh $(u, v)$ có trọng số $w$ vào đồ thị, sau đó có thể loại bỏ tối đa một cạnh để thu được cây khung nhỏ nhất mới. Hãy in ra tổng trọng số nhỏ nhất có thể của cây khung sau mỗi đề xuất (nếu $u = v$, cây khung không đổi).
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, Q$. $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ của cây ban đầu. $Q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ của cạnh đề xuất.
Dữ liệu ra
Gồm $Q$ dòng, mỗi dòng là tổng trọng số cây khung nhỏ nhất ứng với truy vấn.
Ví dụ
| Input | Output |
|---|---|
| 5 3 1 2 5 1 3 2 2 4 8 2 5 3 4 5 4 3 4 10 2 2 1 |
14 18 18 |
Giới hạn
$1 \le N, Q \le 10^5$, $1 \le w \le 10^9$.
Community Discussion