2014년 고2 때 KOI에 나갔던 적이 있습니다. 아마 본선까지는 갔었나 그렇습니다.
그런 사정으로 10169번을 풀었는데, 제 풀이랑 똑같은 풀이를 못 찾아서 공유합니다.
문제를 요약하면 그래프의 각 간선에 대해서 해당 간선을 지운 새 그래프의 MST의 비용 구하기입니다.
우선 MST를 찾으면 그 MST에 속하지 않는 간선들은 원래 MST를 쓰면 되므로, 트리에 속하는 간선을 지웠을 때만 풀면 됩니다.
트리에 속하는 한 간선을 지웠을 때 트리가 두 부분으로 나눠지는데, 이 나눠진 두 부분을 잇는 간선 중에서 가중치가 최소인 것을 골라서 추가하면 간선 지운 새 그래프의 MST가 됨을 증명할 수 있습니다.
어떤 한 간선 u-v를 지운다고 합시다. 트리에 루트를 주어서 오일러 투어를 해놓았다고 치고, v가 u의 부모라고 합시다. 그러면 나눠진 두 부분은 u가 속하는 부분은 u의 서브트리이므로 번호가 연속이고, v가 속하는 부분도 전체에서 u의 서브트리를 뺀 그 왼쪽과 오른쪽 부분이므로 번호가 거의 연속입니다. 이 뒤로는 왼쪽과 오른쪽을 대칭으로 처리하면 되므로 왼쪽만 설명합니다.
이제 왼쪽과 오른쪽 부분을 따로 생각해서, 왼쪽 부분과 u의 서브트리를 잇는 간선 중 가중치가 최소인 것을 찾고자 합니다. 각 u에 대해서 왼쪽 부분의 길이가 다르므로, 왼쪽 부분의 길이를 점차 늘려가면서 현재 왼쪽 부분 길이에 대응하는 u들을 처리합니다.
우선 구간 최소값을 구할 수 있는 point update range query가 되는 자료구조인 세그먼트 트리를 준비합니다.
왼쪽 부분의 길이를 하나 늘리는 과정에서, 새로 추가되는 정점을 p라 합시다. 그러면, p에 연결되어있는 MST에 속하지 않는 모든 간선 p-q(가중치 w)에 대해, 세그에서 q 위치를 w이하로 갱신합니다.
이제 u가 주어지면, u의 서브트리의 번호 범위 lo~hi에 대해서, 세그에 lo~hi 쿼리를 합니다. 그러면 세그에 들어간 q가 lo~hi에서 속하는 것이고, p가 왼쪽 부분에 속하므로, 왼쪽 부분과 u의 서브트리를 잇는 간선 최소인 가중치를 찾을 수 있습니다.

댓글 댓글 쓰기