P3206 [HNOI2010] City Construction

The PS Kingdom is a large country with many cities. King Louis has racked his brains over urban transportation. Louis can build roads between certain pairs of cities, and building roads between different pairs costs different amounts. Louis wants to build the fewest roads so that all cities in the country are connected. However, due to certain factors, the cost to build roads between cities changes over time. Louis will continuously receive notifications that the construction cost of some road has changed. He hopes that after receiving each notification, he can immediately know the minimal total cost to connect all cities. Louis has decided to ask you for help with this task.

The first line contains three integers $n, m, q$, representing the number of cities, the number of roads that can be built, and the number of notifications, respectively. The next $m$ lines: on the $(i + 1)$-th line there are three integers $x_i, y_i, z_i$, meaning the cost to build a road between city $x_i$ and city $y_i$ is $z_i$. Then the next $q$ lines: each line contains two integers $k, d$, meaning the construction cost of the $k$-th road is updated to $d$ (that is, set $z_k$ to $d$).

Output contains $q$ lines. On the $i$-th line, output the minimal total cost to make all cities connected after processing the first $i$ notifications.

Constraints - For $20\%$ of the testdata, $n \le 10^3$, $m, q \le 6 \times 10^3$. - For another $20\%$ of the testdata, $n \le 10^3$, $m \le 5 \times 10^4$, $q \le 8 \times 10^3$. The updated cost will not be lower than the previous cost. - For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$, $1 \le m, q \le 5 \times 10^4$, $1 \le x_i, y_i \le n$, $0 \le z_i \le 5 \times 10^7$. Translated by ChatGPT 5