https://www.acmicpc.net/problem/10637
기본 접근법
- MST를 구성한다.
- 사용하지 않은 간선을 모아둔다.
- i번째 간선이 MST에 사용되지 않았으면 => MST값
- i번째 간선이 MST에 사용되었으면 => MST에서 i번째 간선을 제거했을때 최소값 판단
- i번째 간선을 제거했을때 자식 노드들과 그 외의 노드를 연결할 수 있는 간선(사용하지 않은 간선들) 중 최소값을 찾으면 됨
- 최소값을 어떻게 찾을 것인가?
처음 접근법(시간초과)
- 오일러투어테크닉(ETT)을 사용하면
- base 노드의 자식들의 범위를 알 수 있음
- target 노드가 base 노드의 자식인지 알 수 있음
- MST 구성 후 DFS 수행 후 leaf node에서 올라가면서
- MST에 사용하지 않은 간선 중 자식 노드와 연결이 되었던 모든 간선 merge
- 지금 처리중인 노드와 연결이 되는 간선 추가(merge)
- 간선이 자식 내부에서만 연결된 것들 삭제(양쪽 노드가 모두 자식 노드에 속하는지로 판단)
- 처리가 완료된 간선중 최소값 탐색
- 최소값이 존재하면 MST 값 - i번째 간선의 크기 + 방금 구한 최소값
- 존재하지 않으면 : MST 구성이 안되므로 -1
- 간선을 계속 merge, merge 하므로 시간 초과 발생
최종 접근법
- merge에서 시간초과가 발생하는 부분을 어떻게 해결할지 고민
- 간선은 노드로 매핑함. 노드에 간선의 값이 들어가도록. tr[a] = w, tr[b] = w
- 노드로 구간트리 구성(최소값)
- 자식 노드는 적절히 구성된 상태를 유지함.
- 적절한 간선들로만 노드가 구성되어야함
- 적절한 간선 = 자식노드와 외부 노드를 연결시켜주는 간선
- 의미있는 간선 중에서 최소값을 구해나감
- i 번째 간선 삭제시 자식 노드와 외부 노드가 연결 될 수 있는 간선중 최소값
- 자식노드를 알 수 있고
- 자식노드와 연결된 간선을 알 수 있고
- 간선의 크기를 알 수 있고
- 최소값을 알 수 있음
- 노드에 여러개의 간선이 연결된 경우 최소값만 담기위해 우선순위큐 할당
- pq[a] = 1, 2, 10, 14, ...
- tr[a] = 1
- 구간 트리에는 최소값만 넣기위하여
- 간선이 쓸모가 없어지면 우선순위큐에서 삭제
- 간선이 쓸모 없어지는 순간은 간선 양 끝 노드의 조상들이 만나는 순간임 : LCA
- LCA에 도달하는 순간 해당 간선은 완전히 자식 노드에 속하게 됨
- MST에 사용하지 않는 간선들이 삭제될 시점을 미리 구해서(LCA) 담아둠
- 각 노드에 도달시
- 삭제를 해야할 간선들 확인
- 삭제 처리 및 우선순위 큐 갱신 (<간선크기, 간선번호>)
- 구간트리 갱신
- 자식 노드 중 최소값 탐색(구간트리)
newbieski