23314번 - Minimum Spanning Cactus

[그림] Cactus Graph 예시

선인장 그래프(cactus graph)는 모든 간선이 최대 한 개의 사이클에 속한 연결된 무방향 그래프다. 즉, 임의의 서로 다른 두 사이클이 최대 하나의 공통 정점을 가지는 무방향 연결 그래프를 의미한다.

신장 부분 그래프(spanning subgraph)는 기존 그래프의 모든 정점을 포함하는 부분 그래프(subgraph)를 의미한다. 신장 부분 그래프(spanning subgraph)가 선인장 그래프라면 이를 신장 선인장(spanning cactus)이라고 정의한다. 그래프의 간선에 비용이 주어질 때, 간선의 비용의 합이 최소인 신장 선인장(spanning cactus)을 최소 신장 선인장(minimum spanning cactus)으로 정의한다.

정점이 $N$개, 비용이 있는 무방향 간선 $M$개 있는 선인장 그래프가 주어진다. 모든 정점에는 $1$부터 $N$까지 번호가 붙어있다. 우선 주어진 선인장 그래프의 최소 신장 선인장의 비용을 출력하고 다음 쿼리를 수행하는 프로그램을 작성해보자.

• $u$ $v$ $d$ : 정점 $u$와 정점 $v$를 잇는 간선의 비용을 $d$로 바꾸고, 최소 신장 선인장의 비용을 출력한다.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 쿼리의 개수 $Q$가 주어진다. ($2 \le N \le 100\,000$, $N-1 \le M \le 150\,000$, $1 \le Q \le 100\,000$)

두 번째 줄부터 $M$개의 줄에 걸쳐서 간선을 나타내는 $(x,y,c)$가 순서대로 주어진다. $x$와 $y$는 간선의 양 끝 정점을 의미하고, $c$는 간선의 가중치를 의미한다. 두 정점 사이에 두 개 이상의 간선이 있는 경우는 주어지지 않는다. ($1 \le x, y \le N$, $-10^9 \le c \le 10^9$)

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

첫 번째 줄에는 처음에 주어진 선인장 그래프의 최소 신장 선인장의 비용을 출력한다.

두 번째 줄부터 $Q$개의 줄에 걸쳐서 쿼리의 결과를 출력한다.