BOJ 23314 - Minimum Spanning Cactus

BOJ 23314 - Minimum Spanning Cactus

아…….. 가중치가 변경 후에 그대로 유지되는게 아닌 다시 되돌리는 줄 알고 1시간동안 맞왜틀 하고있었다.

각 BCC를 구한다음에 그 BCC의 모든 가중치 합과 들어가는 모든 가중치들을 multiset에 관리한다.

가중치가 관리되며 BCC에서 가장 가중치가 큰 간선이 양수이고 싸이클일 때만 그 간선을 삭제해주는 방식으로 $O(Q(\log N))$ 으로 모든 쿼리를 처리해주도록 하자.