Elytra

실제 이동 시간에 $2$를 곱한 값을 비용으로 사용하자. 길이가 $w$인 간선을 가속 상태로 지나면 비용은 $w$, 일반 상태로 지나면 비용은 $2w$이다.

[서브태스크 1] $N\leq10$ (7점)

이 서브태스크에서는 산책 자체를 최단 경로 문제로 바꿀 수 있다.

시작점 $s$를 고정하고 상태를 $(M,p,v,t)$로 둔다.

• $M$: 지금까지 한 번 이상 지난 간선들의 집합
• $v$: 현재 정점
• $p$: 바로 전에 있던 정점. 시작 상태에서는 별도의 값으로 둔다.
• $t$: 현재 가속 상태인지 여부

현재 정점 $v$에서 이웃 $u$로 이동한다고 하자. $u=p$이면 방금 지나온 간선으로 즉시 돌아가는 U턴이다. 이 경우 $v$에 폭죽 발판이 없으면 일반 상태로 출발하고, 발판이 있으면 속도를 잃은 직후 폭죽을 사용하므로 가속 상태로 출발한다. $u\neq p$이면 출발 상태는 현재 상태와 같다.

간선을 지난 뒤 $u$에 폭죽 발판이 있으면 다음 상태는 가속 상태가 된다. 이동 비용은 출발 상태가 가속이면 $w$, 일반이면 $2w$이다.

초기 상태는 $(0,\bot,s,A[s])$이다. 모든 간선을 지난 뒤 다시 $s$에 도착한 상태까지의 최단 거리를 다익스트라 알고리즘으로 구한다. 모든 시작점 $s$를 시도한 값의 최솟값이 답이다.

방문한 간선 집합은 $N-1$비트로 저장할 수 있다. 상태 수는 $O(2^N N^2)$이다.

[서브태스크 2] $N\leq15$ (13점)

앞 풀이에서 시작 상태를 제외하면 $p$와 $v$는 항상 인접하다. 따라서 두 정점 번호를 따로 저장할 필요가 없다.

각 방향 간선 $p\to v$에 번호를 붙이고, 상태를 $(M,e,t)$로 둔다. 여기서 $e$는 마지막으로 지난 방향 간선이다. 시작 상태만 별도로 처리한다.

트리의 방향 간선은 $2(N-1)$개이므로 한 간선 집합에 대해 가능한 위치 상태가 $O(N)$개로 줄어든다. 전이는 방향 간선의 끝점에서 다음 방향 간선을 고르는 방식으로 만든다. 다음 방향 간선이 현재 방향 간선의 역방향이면 U턴이고, 아니면 U턴이 아니다.

시작점별 다익스트라 알고리즘의 상태 수는 $O(2^N N)$이고, 전체 시간은 대략 $O(2^N N^3\log(2^N N))$이다.

[서브태스크 3] $N\leq50$ (34점)

지수적인 탐색 대신 트리의 부분 산책을 합치는 DP를 만든다. 이 단계에서는 뒤에서 사용할 일정한 증가 성질은 필요하지 않다.

시작점 정리

폭죽 발판이 하나도 없다면 상태는 항상 일반 상태이다. 시작점으로 돌아오는 산책은 각 간선을 양방향으로 적어도 한 번씩 지나야 하므로 답은 $4\sum_e w_e$이다.

폭죽 발판이 하나라도 있다면 시작점은 폭죽 정점으로 잡을 수 있다. 최적 산책에서 처음 폭죽 정점에 도착한 시점부터 이동 순서를 순환시키면, 새 산책은 가속 상태로 시작하고 비용은 증가하지 않는다.

폭죽 정점 $x$를 인접 간선마다 서로 다른 복사본으로 나눈다. 각 복사본은 해당 간선 하나에만 연결된 폭죽 리프이다. 원래 $x$에 도착할 때마다 가속 상태로 초기화되므로, 서로 다른 인접 간선 쪽 산책은 독립적으로 분리한 뒤 다시 이어 붙일 수 있다. 따라서 분리해서 얻은 트리들의 답을 각각 구해 더하면 된다.

이하 분리해서 얻은 트리 하나만 생각한다. 이 트리에서는 모든 폭죽 정점이 리프이다.

red와 blue

가속 상태의 이동을 red, 일반 상태의 이동을 blue라고 부르자.

폭죽이 없는 내부 정점에서 들어온 간선으로 즉시 돌아가는 이동은 제거할 수 있다. 그 이동은 다른 간선의 피복에 도움을 주지 않고, 이후 상태만 일반 상태로 만들 수 있기 때문이다.

따라서 내부 정점에서는 이동 색이 유지된다. 색이 바뀌는 곳은 리프뿐이다.

• 폭죽 리프에서는 blue로 들어와도 red로 나갈 수 있다.
• 일반 리프에서 U턴하면 red가 blue로 바뀐다.

balance

트리를 임의의 내부 정점에서 루팅한다. 정점 $v$의 서브트리에서 부모 방향으로 더 이어져야 하는 red 경로의 순증가량을 balance라고 하자.

balance가 $+k$이면 폭죽 리프에서 시작한 red 경로 $k$개가 부모 쪽으로 더 나가야 한다. balance가 $-k$이면 일반 리프에서 끝나야 하는 red 경로 $k$개를 부모 쪽에서 더 받아야 한다.

balance가 $0$이 아니면 경계에서 필요한 구조가 하나로 정해진다. balance가 $0$일 때만 다음 다섯 경우를 구분한다.

• $Z_E$: 아직 아무 구조도 없다.
• $Z_R$: 부모 경계에 red만 드러난다.
• $Z_B$: 부모 경계에 blue만 드러난다.
• $Z_C$: red와 blue가 모두 있고 서로 연결되어 있다.
• $Z_S$: red와 blue가 모두 있지만 서로 분리되어 있다.

$P_v[k]$를 balance $+k$인 최소 비용, $N_v[k]$를 balance $-k$인 최소 비용으로 둔다.

폭죽 리프에서는 $Z_R=0$이고 $P[k]=0$이다. 일반 리프에서는 $Z_B=0$이고 $N[k]=0$이다. 내부 정점은 자식을 합치기 전에 $Z_E=0$인 상태에서 시작한다.

분리된 트리 전체의 리프 수를 $L$이라 하자. 루트에서는 balance가 $0$이어야 하므로 $|k|\leq L$인 상태만 저장한다. 어떤 경계에서 $|k|>L$이라면 같은 종류의 리프에서 나온 경로가 중복되고, 반대쪽에도 이를 상쇄하기 위한 중복 경로가 존재한다. 양쪽에서 하나씩 제거해도 간선 피복은 유지되며 비용은 증가하지 않는다. 이 과정을 반복하면 $|k|\leq L$인 최적해를 얻을 수 있다.

부모 간선 붙이기

길이가 $w$인 부모 간선을 붙인다고 하자.

balance의 절댓값이 $k$이면 그 간선을 red로 $k$번, blue로 $k$번 지나므로 $3wk$를 더한다. $Z_R$에는 red 왕복 비용 $2w$, $Z_B$에는 blue 왕복 비용 $4w$, $Z_C$와 $Z_S$에는 두 색의 왕복 비용 $6w$를 더한다.

두 부분 합치기

두 nonzero balance를 합치면 정수처럼 더한다. 양수와 음수가 정확히 상쇄되면 red와 blue가 이어지므로 $Z_C$가 된다.

balance가 $0$인 상태끼리는 다음 규칙을 사용한다.

• $Z_E$는 항등원이다.
• $Z_R$끼리는 $Z_R$, $Z_B$끼리는 $Z_B$이다.
• $Z_R$과 $Z_B$를 합치면 $Z_S$이다.
• $Z_S$에 $Z_R$, $Z_B$, $Z_S$를 합치면 $Z_S$이다.
• $Z_C$를 비어 있지 않은 상태와 합치면 $Z_C$이다.

두 부분의 모든 상태쌍을 확인하여 결과 상태를 갱신한다. 한 병합에 $O(L^2)$이 들고, 전체 시간은 $O(NL^2)$, 메모리는 $O(NL)$이다.

[서브태스크 4] $N\leq100$ (51점)

서브태스크 3의 DP에서 각 정점마다 길이 $2L+5$인 배열을 전부 초기화하면 불필요한 작업이 많다. 현재까지 합친 자식들이 만들 수 있는 balance 구간만 유지한다.

자식 하나를 새로 합칠 때 기존 구간과 자식 구간의 상태쌍만 순회한다. 다섯 개의 $Z$ 상태는 별도로 상수 시간에 처리한다. 또한 비용이 무한대인 상태는 반복문에서 건너뛴다.

상태 정의와 전이는 바뀌지 않는다. 시간 복잡도는 여전히 $O(NL^2)$이지만, 실제 순회 범위는 각 부분에서 도달 가능한 balance 구간으로 제한된다.

[서브태스크 5] $N\leq400$ (72점)

같은 DP를 사용하되, 병합 순서를 정리한다.

각 정점의 자식들을 서브트리 리프 수가 작은 순서로 합친다. 두 배열을 합칠 때는 더 짧은 배열을 바깥 반복문에 둔다. 각 정점의 DP는 자식 처리가 끝난 뒤 부모에게 넘기고, 더 이상 사용하지 않는 자식 배열은 즉시 버린다.

한 병합에서 확인하는 상태쌍 수는 두 부분의 도달 가능한 balance 개수의 곱이다. 전체 시간은 $O(NL^2)$, 메모리는 $O(NL)$이다. $L\leq N$이므로 각각 $O(N^3)$과 $O(N^2)$이다.

[서브태스크 6] $N\leq2\,000$ (100점)

$O(N^3)$ 풀이의 병목은 긴 balance 배열의 뒤쪽까지 모두 저장하고 합치는 것이다. 배열의 뒤쪽은 일정한 차이로 증가한다.

정점 $v$의 서브트리에 있는 폭죽 리프 수를 $B_v$, 일반 리프 수를 $D_v$라 하자. 또한 $s_v^+$를 $3$에 $v$에서 가장 가까운 폭죽 리프까지의 거리를 곱한 값, $s_v^-$를 $3$에 가장 가까운 일반 리프까지의 거리를 곱한 값으로 둔다. 해당 종류의 리프가 없으면 무한대로 둔다.

$k\geq B_v$이면 $P_v[k+1]-P_v[k]=s_v^+$이다. 대칭적으로 $k\geq D_v$이면 $N_v[k+1]-N_v[k]=s_v^-$이다.

첫 번째 식을 증명하자. $k>B_v$개의 미완성 red 경로가 있으면 같은 폭죽 리프에서 시작한 경로가 적어도 두 개 있다. 그중 하나를 그 리프에서 $v$까지 제거해도 같은 경로가 하나 남으므로 필요한 간선 피복과 연결은 유지된다. 제거되는 비용은 그 리프까지 거리의 $3$배이며 $s_v^+$ 이상이다.

반대로 가장 가까운 폭죽 리프에서 $v$까지 경로 하나를 더 만들면 정확히 $s_v^+$의 비용으로 balance를 하나 늘릴 수 있다. 두 방향을 합치면 차이가 정확히 $s_v^+$임을 얻는다. $N_v$도 같은 방식으로 증명된다.

따라서 실제로 저장할 값은 $P_v[1],\ldots,P_v[B_v]$와 $N_v[1],\ldots,N_v[D_v]$뿐이다. 그 뒤의 값은 마지막 저장값과 일정한 증가량으로 계산한다.

$P_v$의 저장 구간은 반드시 $B_v$를 기준으로 해야 한다. 일반 리프 수 $D_v$를 기준으로 자르면, 아직 사용하지 않은 폭죽 리프를 처음 사용하는 비용과 이미 사용한 가까운 폭죽 리프를 반복하는 비용의 순서를 잘못 판단할 수 있다.

압축된 배열 병합

두 부분의 리프 수를 각각 $x,y$라 하자.

저장된 구간끼리의 상태쌍은 직접 확인한다. 한쪽만 일정 증가 구간에 있는 경우에는 앞쪽 최솟값이나 뒤쪽 최솟값을 미리 계산하여 한 번의 조회로 처리한다.

부호가 반대인 두 상태를 합칠 때는 저장 구간-저장 구간, 저장 구간-일정 증가 구간, 일정 증가 구간-저장 구간, 일정 증가 구간-일정 증가 구간으로 나눈다. 가운데 두 경우는 뒤쪽 최솟값으로 처리한다. 마지막 경우에는 두 증가량이 음수가 아니므로 조건을 만족하는 가장 작은 인덱스쌍만 확인하면 된다.

한 병합의 시간은 $O(xy+x+y)$이다.

모든 병합의 $xy$ 항을 합치자. 두 리프의 순서 없는 쌍 하나는 그 두 리프가 처음 같은 부분에 들어오는 병합에서 한 번만 처리된다. 따라서 모든 곱 항의 합은 $O(L^2)$이다. 선형 스캔의 총합은 $O(NL)$이고 $L\leq N$이다.

분리된 모든 트리의 정점 수와 리프 수의 합은 $O(N)$이므로 전체 시간 복잡도는 $O(N^2)$이다. 모든 정점의 DP를 저장해도 메모리 복잡도는 $O(N^2)$ 이하이다.

루트에서 답 구하기

분리된 트리의 루트에서는 balance가 $0$이어야 한다. red만 있는 연결된 산책, blue만 있는 연결된 산책, 두 색이 연결된 산책은 모두 가능하므로 답은 $\min(Z_R,Z_B,Z_C)$이다.

$Z_S$는 두 구조가 한 산책으로 연결되지 않은 상태이므로 사용할 수 없다. $Z_E$는 분리된 트리에 간선이 하나도 없을 때만 비용 $0$으로 허용한다.

각 분리된 트리의 답을 모두 더하면 원래 트리의 답이 된다.

Solution written by GPT5.6