BOJ 2927. 남극 탐험
문제 해석
간선이 없고 정점마다 가중치가 부여된 그래프가 주어질 때 3종류의 명령을 offline으로 처리하라.
bridge A B: 정점 \(A\)부터 \(B\)까지 경로가 있는지 없는지 보고하고, 없으면 \(A\), \(B\)를 잇는 간선을 추가한다.penguins A X: 정점 \(A\)의 가중치를 \(X\)로 바꾼다.excursion A B: 정점 \(A\)부터 \(B\)까지 경로가 있으면 그 가중치 합을 출력하고, 없으면 없다고 보고한다.
접근
bridge 명령 시 경로가 없을 때에만 간선을 추가하기 때문에 그래프에 사이클(닫힌 경로)이 생길 일이 없다. 즉 그래프는 언제나 forest이며, 그러면 penguins와 excursion 명령은 각각 정점 업데이트와 경로 합 쿼리로 이해할 수 있다.
우선 명령들을 순서대로 훑으며 penguins는 무시하고 bridge와 excursion만 수행해서 최종 시점의 forest를 구한다. 간선이 생기기만 하고 사라지지는 않으므로 경로 존재 여부는 union-find(disjoint sets)로 추적하면 된다. 구한 forest에 HLD를 써서 경로 쿼리를 위한 준비를 하고, 입력받은 초기 가중치로 segment tree를 하나 만들자. HLD에서 정점들이 새롭게 넘버링되므로 가중치 값들도 이 넘버링에 따라 재배열해서 segment tree에 넘겨줘야 한다는 점을 유의하자.
이렇게 하면 모든 준비가 끝나고, 이제 다시 한 번 명령들을 차례로 훑으며 실제로 수행하면 된다. 처음에 썼던 union-find를 초기화하고 다시 구축하면서 경로 존재를 판단하고, 가중치 변경과 경로 합은 chain 정보와 segment tree를 이용해 처리하자.