Cập nhật cây khung nhỏ nhất

General
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved