2021.07.27 problem solving

CCC 2017 S2. High Tide Low Tide

입력으로 들어온 수열을 정렬한 후, 만조때는 중앙값부터 감소하는 순서대로, 간조일때는 중앙값부터 증가하는 순서대로 출력합니다.

$n = 2k + 1$ 이면: a[k+1] a[k+2] a[k] a[k+3] ... a[2] a[2k+1] a[1]

$n = 2k$ 이면: a[k] a[k+1] a[k-1] a[k+2] ... a[1] a[2k]

VKOShP 2017 A. Tourism

웬만하면 굉장히 큰 답을 찾을 수 있다는 게 핵심 포인트입니다.

만약 $S[1] = S[N]$ 이면 답은 $[1, N-1], [2, N]$ 입니다.

아니면, $S[1] = S[2] = \ldots = S[i]$ 가 만족하는 최대 $i$ 와 $S[N-j+1] = S[N-j+2] = \ldots = S[N]$ 이 만족하는 최대 $j$ 를 찾습니다. 답은 $[i+1, N-1], [i+2, N]$ 혹은 $[1, N-j-1], [2, N-j]$ 입니다.

이보다 더 좋은 답이 존재한다면, 두 구간 모두 $S[1, i], S[N-j+1, N]$ 에 걸치게 될 건데, 그러한 구간 중 길이가 같은 구간에서의 관광지의 개수는 항상 달라질 수 밖에 없습니다. 같은 길이의 구간을 왼쪽에서 오른쪽으로 움직여 보면 항상 관광지의 개수가 1씩 증가할 것이기 때문입니다.

Facebook Hacker Cup 2020 Qual B. Alchemy

한 연산은 A 하나, B 하나를 제거합니다. 고로 연산을 통해서 모든 돌을 제거하기 위해서는 A의 개수와 B의 개수의 차가 1이어야 합니다.

만약 A의 개수와 B의 개수의 차가 1이고, 배열에 3개 이상의 돌이 있다면, AAA / BBB 형태가 아닌 연속한 세 돌이 무조건 존재합니다. 그래서 연산을 항상 수행해서 돌의 개수를 2개씩 줄일 수 있고, 이를 반복할 수 있습니다.

그래서 A의 개수와 B의 개수의 차가 1인지를 판별하는 문제고 이는 반복문으로 구현하면 됩니다.

AMPPZ 2012. 크리스 마틴

입력에서 ACGT 중 가장 적게 등장하는 문자를 그냥 N번 찍으면 됩니다.

왜냐면... 위 알고리즘이 반환한 LCS를 $x$ 라고 하고 이보다 더 작은 답 $y$ 가 있다고 합시다. 만약 ACGT 중 한 문자라도 y번 초과로 등장한다면, 그냥 해당 문자들만 모아서 $y+1$ 이상의 common subsequence를 찾을 수 있으니 가정에 모순입니다. 고로 각 문자가 최대 $y$ 번 등장하고, 문자열의 길이는 최대 $4y$ 가 됩니다. 그런데, $4x \le N$ 이니, $4y \le N - 4$ 입니다. 고로 모순입니다.

CCO 2019. Interval Collection

최대 공통 부분구간의 길이를 최소화하는 조건만 있다면, 그냥 $T = S$ 로 두면 됩니다. 이 경우, 그 길이는

• $max(l) < min(r)$ 일 경우 $min(r) - max(l)$
• 아닐 경우 0

입니다.

현재 경우가 첫 번째라고 합시다. $min(r) - max(l)$ 이라는 값을 얻고 싶으면, 전체에서 $r$ 을 최소로 하는 구간 하나와 $l$ 을 최대로 하는 구간 하나를 $T$ 에 두면 됩니다. $r, l$ 각각에 대해서 두 개 이상 둘 필요가 없고, 두어 봤자 합집합의 길이만 늘어납니다. 고로 Naive하게는 이 조건을 만족하는 1개 혹은 2개의 구간을 모두 해 본 후 $max(r) - min(l)$ 의 최솟값을 취하는 것입니다.

$r$을 최소로 하는 구간을 가져가면, $min(l)$ 은 이 구간의 $l$ 값과 동일합니다. $l$ 을 최대로 하는 구간의 값보다 무조건 작거나 같기 때문입니다. 같은 이유로, $l$ 을 최대로 하는 구간을 가져가면 $max(r)$ 은 이 구간의 $r$ 값과 동일합니다. 고로

• $r_i = min(r)$ 을 만족하는 구간 중 $l_i$ 최대
• $l_i = max(l)$ 을 만족하는 구간 중 $r_i$ 최소

를 독립적으로 계산하면 전체 문제가 해결됩니다. 이건 $O(N)$ 에 쉽게 할 수 있습니다.

현재 경우가 두 번째라고 합시다. 겹치지 않는 두 구간 쌍 $[l_1, r_1], [l_2, r_2]$ 를 골라서 ($r_1 \le l_2$) $r_2 - l_1$ 을 최소화하는 것이 문제입니다. 교집합이 0인 경우, 항상 겹치지 않는 두 구간 쌍이 존재하기 때문에, 집합 크기가 2인 경우만 해 보면 됩니다. 이것 역시 $O(N^2)$ 에 할 수 있습니다.

이제 Naive한 풀이를 생각했으니 자료구조를 사용하여 최적화해줍니다. 오프라인으로 쿼리를 처리하며, 입력으로 주어진 모든 구간을 처음에 받은 후, 구간을 삭제하지 않고 toggle-on, toggle-off 만 해 주는 것으로 해결합니다.

• 구간을 $r_i$ 순으로 정렬합시다. $r_i = min(r)$ 을 만족하는 구간들은 연속하여 존재하니, $l_i$ 에 대한 max segtree를 두어 최댓값을 찾습니다.
• 구간을 $l_i$ 순으로 정렬합시다. $l_i = max(l)$ 을 만족하는 구간도 다른 세그트리에서 동일하게 합니다.
• 각 위치에 대해서, 해당 위치에서 시작하는 / 끝나는 구간의 최소 $r$ / 최대 $l$ 을 set 등으로 관리합니다. 이 값을 $minRight[i], maxLeft[i]$ 라고 하면, $-maxLeft[i] + minRight[j]$ 의 최솟값을 모든 $i \le j$ 에 대해서 계산하는 문제가 됩니다. 이는 연속 합을 저장하는 세그먼트 트리처럼 해 주면 됩니다.

Ptz Summer 2020 Day2D. Delete Two Vertices Again

주어진 그래프의 DFS spanning tree $T$ 를 찾습니다. 그래프의 모든 간선 $(v, r)$ 은 $T$ 상에서 한 쪽이 다른 쪽의 조상이라는 관계를 만족합니다. $r$ 을 루트에서 가까운 쪽, $v$ 를 루트에서 먼 쪽이라고 합시다.

간선 $v, r$ 을 지웠을 때 나올 수 있는 컴포넌트는 다음과 같습니다.

• $T$ 기준 $v$ 의 자식 노드들의 서브트리 $L_i$
• $v, r$ 사이 경로에 있는 컴포넌트 $M$ ($v, r$ 이 인접할 경우 존재하지 않음)
• $T$ 기준 $v$ 방향을 제외한 $r$ 의 자식 노드들의 서브트리 $MT_i$
• $T$ 기준 $r$ 의 부모 방향 서브트리 $T$

이렇게 보면 너무 많은데, 다음과 같은 아이디어로 단순화할 수 있습니다. 만약 $r$ 이 절점이 아니라면, $T$ 와 $MT_i$ 들은 항상 연결되어 있습니다. 그래서 $MT_i$ 에 대해서 따로 고려할 필요가 없이, $T$ 에 대해서만 고려해 줘도 상관이 없습니다. $r$ 이 절점이라면, $v, r$ 을 지웠을 때도 그래프가 연결될 수 있는 방법은 단 하나입니다: $v$ 가 $r$ 에 인접하며, $v$ 에서 $r$ 이 아닌 다른 정점에 인접한 간선이 존재해서는 안됩니다. 이 경우를 따로 예외처리 해 주면, $MT_i$ 에 대해서 고려할 필요가 없어집니다.

남은 컴포넌트들간의 연결 관계는 다음과 같이 판별합니다. $L_i, M, T$ 가 공집합인 경우는 예외처리 해서, 셋 모두 공집합이 아니라고 가정합시다.

$L_i$ 에서 $M, T$ 간에 간선이 있는지를 보기 위해서는, $L_i$ 에서 뻗어오는 Back edge들 중에 가장 높게 올라오는, 그리고 가장 낮게 올라가는 간선을 찾으면 됩니다. 여기서, 가장 낮게 올라가는 간선이라는 것은 $v$ 에서의 서브트리를 무시하고, $v$ 의 조상으로는 올라오지만 낮게 올라가는 간선을 의미합니다. 가장 높게 올라가는 간선은 단순 Tree DP로 계산할 수 있으나, 낮게 올라가는 간선은 $v$ 의 조상으로는 올라와야 한다는 조건 때문에 그렇게 쉽게 되지는 않습니다. 각 정점에 대해서 서브트리 back edge들을 깊이 순으로 heap에 넣은 후, small-to-large를 쓰거나, Leftist heap같은 mergeable heap을 구성하는 식으로 계산할 수 있습니다.

$L_i$ 에서 뻗어오는 Back edge들 중에 가장 높게 올라오는, 그리고 가장 낮게 올라가는 간선을 찾았을 때

• 찾을 수 있는 간선이 없거나
• 찾을 수 있는 간선이 모두 $r$ 에 인접하면

$L_i$ 는 $M, T$와 disconnected되었으니 그래프는 연결되지 않았습니다. 아니면 $M, T$ 중 하나와는 인접합니다.

두 번째로, $M, T$ 간에 연결이 되어 있는지를 확인해야 합니다. 두 가지 경우가 있습니다: $M, T$ 간에 직접 간선이 있거나, $L_i$ 중 하나가 두 집합에 동시에 인접한 케이스입니다.

$M, T$ 간에 간선이 있다는 것은 $r$ 의 조상 방향으로 back edge가 존재하는 정점이 $M$ 에 있다는 것입니다. $M$ 에 있는 정점은 $r$ 에서 $v$ 방향 자식의 서브트리에 속하지만, $v$ 의 서브트리에는 속하지 않습니다. 고로 $M$ 에 있는 정점을 DFS ordering 상에서 두 개의 구간으로 표현할 수 있습니다. 세그먼트 트리를 사용하여, 각 정점에서 가장 높게 올라가는 back edge를 저장하면, $M$ 과 $T$ 간에 간선이 있는지를 볼 수 있습니다.

$L_i$ 중 하나가 두 집합에 동시에 인접하다는 것은, $L_i$ 의 가장 높은 간선이 $r$ 의 조상이고 가장 낮은 간선이 $r$ 의 자식이라는 뜻입니다. $L_i$ 의 두 간선의 깊이를 구간으로 보면, 결국 $r$ 을 포함하는 구간의 존재 여부를 따지는 문제와 동일하여, 이분 탐색이나 fenwick tree 등등을 사용하여 해결할 수 있습니다.

시간 복잡도는 Small-to-large를 사용하면 $O(m \log^2 m)$, Mergeable heap을 사용하면 $O(m \log m)$입니다.

JAG Spring 2015. New Game AI

$i$ 번 챔피언이 $j$ 번 챔피언을 대체할 수 있으면 $cmp(i, j)$ 가 참이라고 하고, 그렇지 않으면 거짓이라고 합시다.

$O(n^3)$ 풀이

각 챔피언을 정점으로 하는 그래프를 만들고, 다음과 같은 방향 간선을 이어줍시다.

• Type 1 간선은 $cmp(i, j)$ 인 모든 $i \neq j$ 에 대해 $i \rightarrow j$ 방향으로 간선을 잇습니다.
• Type 2 간선은 $!cmp(i, j)$ 인 모든 $i \neq j$ 에 대해 $j \rightarrow i$ 방향으로 간선을 잇습니다.

$i \rightarrow j$ 방향으로 Type 1 간선이 있다면 무조건 Type 2 간선이 존재하지만, 그 반대는 성립하지 않습니다. 반대가 성립하지 않는 경우는, 두 챔피언의 방어력(D)이 똑같고 체력(H)의 차가 $C$ 이하인 경우입니다.
여기서 다음과 같은 Theorem이 성립합니다.

Theorem 1. Type 1 간선만을 사용하거나, 맨 마지막 간선을 제외하고 Type 1 간선만을 사용하는 경로를 replacement path 라고 부르자. 어떠한 챔피언 $X$ 가 최종 답이 될 수 있다는 것은, $X$ 에서 다른 모든 챔피언으로 가는 replacement path 가 존재함을 뜻한다.

$\rightarrow$ 방향의 증명은 간단합니다. $X$ 를 답으로 하는 permutation을 생각해 봅시다. 이 permutation에서 중간에 반환값이 된 적이 있는 챔피언의 번호를 $i_1, i_2, \ldots, i_k = X$ 라고 하였을 때, $i_k \rightarrow i_{k-1} \rightarrow \ldots i_1$ 방향으로 가는 Type 1 간선만을 사용하는 Path가 존재합니다. 답이 된 적이 없는 챔피언 $j$에 대해서는, 해당 챔피언과 비교되었던 챔피언 $i_p$ 에서 $j$ 로 가는 Type 2 간선이 존재합니다. 고로 답을 하는 permutation이 이러한 경로에 대응됩니다. replacement path 의 정의가 낯설어 보이지만, 문제에서 수행하는 동작을 생각보다 명확히 표현해 주고 있음을 여기서 관찰할 수 있습니다.

$\leftarrow$ 방향의 증명은 안타깝게도 모르지만, 정황상 사실로 보입니다. 증명을 찾으신 분이 있다면 개인적으로 알려주시면 감사하겠습니다. 일단 여기서는 Type 1 간선만이 있는 경우에 대해서 증명합니다.

Observation 2. Type 2 간선이 없다면, replacement path들을 모아 directed spanning tree를 만들 수 있다.

Lemma 3. Directed tree $T$ 와 $T$ 의 임의의 리프 $x$ 에 대해서, $V(T)$ 의 정점을 포함하며, $x$ 로 시작하고, 문제에서 정의된 비교 과정을 수행했을 때 루트를 반환하는 permutation이 존재한다.

Proof of Lemma 3. 수학적 귀납법을 사용한다. $|V(T)| = 1$ 인 경우 자명하다. 그 외 경우, 루트를 $r$ 이라고 하고, $x$ 방향의 자식을 $child[r][0]$, 그 외 자식을 $child[r][1], \ldots$ 라고 하자. 귀납 가정에 의해, $child[r][0]$ 을 포함하는 서브트리에서, $x$에서 시작하고 서브트리 정점을 모두 포함하며 $child[r][0]$ 을 반환하는 permutation이 존재한다. 이 permutation에서 시작하여, $child[r][1]$의 임의의 리프를 permutation에 붙이기 시작한다. 만약 이 중 하나가 $child[r][0]$ 을 대체한다면, 해당 시점에서 다시 귀납 가정을 사용하여 $child[r][1]$ 을 반환하는 permutation으로 확장시킨다. 그러한 것이 없다면, 단순히 $child[r][1]$ 전체를 bottom-up 순서대로 permutation에 붙여준다. 이를 반복하여 모든 subtree를 소모한다면, 최종적으로 반환값이 $r$ 의 자식 중 하나인 순열을 찾을 수 있다. 이 뒤에 $r$ 을 붙이면, 이 자식은 항상 대체된다.

이를 사용하여 모든 $X$ 에 대해 간단한 DFS를 사용하면 $O(n^3)$ 시간에 문제를 해결할 수 있습니다.

$O(n^2 \log n)$ 풀이

각 $X$ 에 대해서 Type 1 간선만을 사용하여 도달할 수 있는 챔피언을 $O(n \log n)$ 에 계산할 수 있습니다. 나름 잘 알려진 트릭이지만, 다시 한번 소개합니다.

이제부터 편의상 각 챔피언의 스탯을 $(h_i, d_i)$ 라고 두고, 2차원 좌표상의 점으로 간주합니다. 어떠한 $X$ 에 대해서 Type 1 간선만을 사용하여 도달할 수 있는 챔피언은, $h_Y > h_X + C$ 를 만족하거나, $h_X - C \le h_Y \le h_X + C$ 이면서 $d_Y > d_X$ 를 만족합니다. 각 $X$에 대해서, 이를 만족하는 아직까지 방문하지 않은 정점 $Y$ 하나를 $O(\log n)$ 시간에 찾을 수 있으면, 전체 DFS/BFS 과정이 $O(n \log n)$ 시간에 해결됩니다.

첫 번째 조건은, 단순히 모든 챔피언을 H 순으로 정렬한 후, 아직 방문 안 된 가장 HP가 큰 챔피언을 two pointers처럼 움직여가면서 관리합니다.

두 번째 조건은, $H$ 가 특정 구간 안에 있는 챔피언 중 $D$ 가 $d_X$ 초과인 아무 챔피언을 찾으면 됩니다. 챔피언의 D를 기준으로 한 maximum segment tree를 만들고, 만약 어떠한 챔피언을 방문하면 segment tree에서 지워줍니다. 이렇게 하면 구간 최댓값이 $d_X$ 초과일 때 항상 원하는 챔피언 하나를 뽑을 수 있습ㄴ다.

여기에 더해서 Type 2 간선을 사용하여 도달할 수 있는 챔피언을 구해야 하는데, Type 1 간선으로 연결되어 있지만 Type 2 간선으로 연결된 챔피언은 DP가 같고 HP 차가 $C$ 이하입니다. 고로 $(h_i, d_i)$ 쌍으로 정렬하면 이러한 챔피언들이 구간을 이루니, 변홧값 배열 등으로 확인할 수 있습니다.

종합적으로 전체 문제가 $O(n^2 \log n)$ 에 해결 됩니다. 여전히 문제를 해결하기에 충분하지 않지만, 세그트리를 사용한 DFS/BFS는 만점 풀이에서도 필요하니 미리 언급해둡니다.

$O(n \log n)$ 풀이

전체 챔피언 중 최소의 HP를 가진 챔피언을 $m$ 이라고 합시다. $h_i \le h_m + C$ 를 만족하는 모든 챔피언들 중 DP가 최소인 챔피언들을 $c$ 라고 합시다. 만약 이러한 챔피언이 여럿 있다면 아무 거나 고릅니다.

다음 사실이 성립합니다.

Observation 4. $c$ 를 반환 값으로 하는 순열이 항상 존재한다. (증명은 Theorem에 의해 자명하며 직접 construct할 수도 있다.)

Observation 5. $c$ 를 Type-1 간선으로 도달할 수 있는 챔피언은 모두 답이 된다.

Proof of Observation 5. Theorem에 의해 $c$ 에서 모든 정점으로 replacement path가 존재하기 때문에 이 경로의 앞에 $c$ 로 간 경로를 붙여주면 된다. 단순 경로가 아니라면 단순 경로로 변환할 수 있다.

Observation 5에 의해, $c$ 를 Type-1 간선으로 도달할 수 있는 챔피언을 모두 $c\text{-visited}$ 라고 정의합시다. 또한, 각각의 DP $d$ 에 대해서, $d_i = d$ 인 원소들 중 HP의 최솟값을 $hpMin[d]$ 라고 정의합시다.

Lemma 6. 만약 $d_i = d$ 인 챔피언이 존재하며 $h_i \le hpMin[d]+C$ 인 챔피언들이 모두 $c\text{-visited}$ 인 $d$ 가 존재한다면, $c\text{-visited}$ 인 챔피언의 집합은 답의 집합과 동일하다.

Proof of Lemma 6. $c\text{-visited}$ 가 아닌 챔피언에 대해서 답이 있다고 합시다. 이 챔피언들은 $d_i = d, h_i \le hpMin[d]+C$ 인 챔피언을 방문하기 위해, 이 챔피언들 중 하나에 Type 1 간선만으로 이루어진 경로를 통해 접근합니다. 그렇게 방문한 챔피언이 $c\text{-visited}$ 이기 때문에 결국 이 챔피언도 $c\text{-visited}$ 이고 이는 가정에 모순입니다.

$c\text{-visited}$ 인 정점들을 $X_c$ 라고 두었을 때, $V - X_C$ 에서 똑같은 방법으로 $c^\prime$ 을 구합니다. 여기서도 $c^\prime$을 Type-1 간선으로 방문할 수 있는 정점들을 모두 $c^\prime\text{-visited}$ 라고 정의할 수 있습니다. 이 정점들 역시 $V - X_C$ 에 있는 모든 정점을 도달할 수 있습니다. 여기서 궁금한 것은, 과연 $X_C$ 에 있는 정점들 역시 여기서 도달할 수 있을까요?

Lemma 7. $c^\prime\text{-visited}$ 인 챔피언은 모두 답이 된다.

Proof of Lemma 7. 모든 유효한 $d$ 에 대해서, $d_i = d, h_i \le hpMin[d] + C$ 이며 $c^\prime$-visited인 $i$ 가 존재한다. 여기서 모든 다른 정점들을 Type 2 간선 하나로 도달할 수 있다.

이를 계속 반복하면, 우리는 $d$ 에 난 "구멍" 을 사용하여 계속 방문한 정점의 집합을 늘리거나, 아니면 더 이상 방문할 수 있는 집합이 없음을 보일 수 있습니다. 고로 이 과정을 계속 반복하면, 전체 문제가 $O(n \log n)$ 시간 복잡도에 해결됩니다.

BOJ 22278. 두 최단 경로

$O(N^2 M)$

각 끝점에 대해 독립적으로 문제를 해결합니다.

Network Flow 관점에서 보면, 이 문제는 시작점에서 끝점으로 2의 유량을 최소 비용으로 흘리는 문제입니다. MCMF 알고리즘을 사용하여 해결할 수 있습니다. 처음 한 번 최단 경로를 찾아준 후, 처음 찾은 최단 경로의 방향과 가중치를 뒤집고, 또 한번 최단 경로를 찾아주면 됩니다.

최단 경로를 Bellman-Ford나 SPFA로 찾으면 $O(NM)$ 시간이 걸립니다.

$O(NM \log M)$

처음 최단 경로를 찾을 때는 Dijkstra's algorithm을 사용하여 $O(M \log M)$ 에 찾을 수 있습니다.

문제는 두 번째 최단 경로를 찾을 때 음수가 나오는 것입니다. 첫 번째 Dijkstra에서 찾은 거리를 $dist[i]$ 라고 하면, 모든 간선 $u \rightarrow v$ 에 대해서 $dist[v] \le dist[u] + w(u \rightarrow v)$ 가 성립합니다.

간선의 가중치를 $w(u \rightarrow v) + dist[u] - dist[v]$ 로 대체하면, 모든 간선의 가중치가 0 이상입니다. 특별히, 시작점에서의 Shortest path tree에 속하는 간선은 $dist[v] = dist[u] + w(u \rightarrow v)$ 이기 때문에 가중치가 0이고, 역변을 취해도 가중치가 0이 됩니다.

이제 이 그래프에서 최단 경로 $v_0(1) - v_1 - \ldots - v_{k-1} - v_k (i)$ 를 구하면, 경로의 가중치 합은 $w(v_0 \rightarrow v_1) + w(v_1 \rightarrow v_2) \ldots w(v_{k-1} \rightarrow v_k) + dist[v_0] - dist[v_k]$ 가 됩니다. $dist[v_0] - dist[v_k]$ 는 상수이니, 이 값을 최소화하는 것과, 원래 그래프에서의 경로 가중치 합을 최소화하는 것은 동일합니다.

결론적으로, (새로운 그래프에서의 최단 경로) + $dist[v_k]$ 가 두 번째로 찾은 경로의 가중치라고 할 수 있습니다. 새로운 그래프의 간선 가중치는 모두 음수가 아니니 Dijkstra's algorithm을 사용할 수 있습니다.

$O(M \log M + MN)$

처음 최단 경로를 찾을 때는, 모든 도착점에 대해서 Dijkstra's algorithm을 사용하여 $O(M \log M)$ 에 찾을 수 있습니다.

두 번째 최단 경로를 찾을 때는, 도착점에 따라서 그래프가 바뀝니다. 만약 도착점이 $v$ 라면, $1$ 에서 $v$ 로 가는 경로 상의 간선의 방향이 뒤집힙니다. 이 때문에 매번 처음부터 Dijkstra를 돌리는 것인데, 그럼에도 불구하고 단 한번 의 Dijkstra's algorithm으로 모든 점까지의 최단 경로를 한 번에 찾습니다. 즉, $dist[v]$ 를 ($s$ 에서 $v$ 로 가는 경로의 방향이 뒤집혔을 때 $v$ 까지의 최단 경로라고 하면), Dijkstra's algorithm을 잘 변형해서 이 $dist[v]$ 를 모든 $v$ 에 대해서 계산합니다.

각 도착점에 대해서 다른 것은 스패닝 트리의 간선 방향 뿐임에 유의하면서 시작합니다. 맨 처음, $1$ 번 정점을 방문합니다. 각 정점을 기준으로, 1번 정점에서는 자신 쪽 서브트리를 제외한 모든 정점을 0의 가중치로 방문할 수 있습니다. 고로 1번 정점을 기준으로 다른 서브트리를 잇는 간선 $(u, v, e)$ 는 모두 1에서 $v$를 직접적으로 잇는다고 생각할 수 있습니다. $u$ 가 다른 서브트리에 있으니 공짜로 방문할 수 있기 때문입니다. 고로, $dist[v] = min(dist[v], e)$ 로 세팅해 주는 것을, 모든 다른 서브트리가 잇는 간선에 대해서 반복합니다. 물론, 1번 정점에서 나가면서 shortest path tree에 속하지 않는 간선들 역시 모두 이를 반복해 줍니다. 이 이후, 다른 서브트리를 잇는 간선들은 더 이상 사용 가치가 없으니, 모두 제거해 줄 수 있습니다. 다른 말로, 1번 정점을 제거한 이후 남는 서브트리에 대해서, 문제를 독립적으로 해결해도 괜찮습니다.

이후에도 이 과정을 반복합니다. 현재까지 방문하지 않은 정점 중 거리가 최소인 정점을 찾습니다. 이 정점을 $x$ 라고 합시다. $x$ 에서 나가는 모든 shortest path tree에 속하지 않는 간선을 먼저 relax해주고 시작합니다. $x$ 를 지우면 $x$ 를 포함하는 서브트리 $S$ 가 $S_1, S_2, \ldots, S_i$ 로 분할되게 되며, 이 중 어떤 것은 $S$ 의 부모 방향을 이을 수도 있습니다. 여기서 다른 서브트리를 잇는 간선 $(a, b, c)$ 를 고려했을 때도, $b$ 를 도착점으로 했을 때 $v$ 에서 $a$ 를 항상 0의 비용으로 갈 수 있음을 관찰할 수 있습니다. 부모 방향이 추가되었음에도 이 성질이 여전히 만족한다는 것이 대단히 흥미로운데, 직접 손으로 확인해 보시면 그 묘미를 느끼실 수 있습니다. 현재 $S$ 에 있는 정점 중 $x$ 보다 1번에서 가까운 정점은 없으니, 이보다 더 간선을 잘 쓸 수 있는 방법은 없으며, 고로 이 경우에도 간선을 지워줄 수 있고, 각 서브트리의 문제는 계속 독립으로 남습니다.

이를 반복해 주면 모든 정점에 대해서 원하는 답을 얻을 수 있습니다. 간선 집합이 다른데도 Dijkstra를 한 번만 돌려도 된다는 사실이 아주 비직관적입니다. 문제의 성질이 굉장히 많은 정점을 0의 가중치로 도달할 수 있게 해 주고, 이를 통해서 서로 다른 서브트리에 있는 간선을 "지워 버릴 수 있다" 라는 강력한 성질을 쓰는 것이 핵심이라고 생각합니다.

이를 단순히 반복해주면 $O(MN \log N)$ 인 것 같지만, 사실 각 정점이 최대 $O(M)$ 번 Relax되기 때문에 간선 집합을 lookup 하는 것이 가장 오래 걸립니다.

$O(M \log M)$

$x$ 에서 나가는 정점을 relax하는 것은 쉽지만, $x$ 에서 다른 서브트리를 잇는 간선을 relax하는 것이 어렵습니다. 하지만 우리는 "다른 서브트리" 를 잇는 간선에만 관심이 있습니다. 즉, 가장 큰 서브트리를 무시해도 모든 관심있는 간선 집합을 찾을 수 있습니다. 하지만 $x$ 에 연결된 서브트리 중 어떤 것이 큰 지 모릅니다. 그래서 모두 다 탐색해 보는데, 하나의 서브트리를 한번에 탐색하지 않고, 매 순간 서브트리에서 방문한 간선을 정확히 하나씩 늘려나갑니다. 이후 하나의 서브트리를 빼고 탐색이 종료되었다면, 이 쪽이 가장 큰 서브트리입니다. Small-to-large의 논리에 의해서 이렇게 했을 때 각 간선이 정확히 $O(\log M)$ 번 탐색됩니다. 구현 시 매번 "방문한 정점" 을 하나씩 늘려서는 안되고, "방문한 간선" 을 하나씩 늘려야 함에 유의해야 합니다.

이상의 내용은 https://www.eecs.yorku.ca/course_archive/2007-08/F/6590/Notes/surballe_alg.pdf 에서 가져왔습니다.