지가르데 경곽폼

1. 코어 경로 위의 그룹으로 축약하기

코어 $A$와 코어 $Z$ 사이의 경로를 순서대로 $V_1,V_2,\ldots,V_M$이라고 하자. 각 정점을 자신과 가장 가까운 코어 경로 정점에 배속하고, $V_i$에 배속된 정점의 수를 $w_i$라고 정의한다. 경로 위의 정점 $V_i$ 자신도 이 그룹에 포함되므로 $w_i$는 항상 1 이상이다.

끊을 수 있는 간선은 코어 경로 위의 간선뿐이다. 따라서 같은 그룹에 속한 정점들은 항상 같은 연결 요소에 남고, 하나의 연결 요소는 연속한 그룹들로 이루어진다. 반대로 $M$개의 그룹을 정확히 $K$개의 비어 있지 않은 연속 구간으로 나누면, 구간 사이의 $K-1$개 간선을 끊어 그 분할을 얻을 수 있다.

같은 그룹에 속한 두 정점의 에너지는 0이다. 서로 다른 $i$, $j$번 그룹 사이에서는 정점 쌍이 $w_iw_j$개이고, 각 쌍의 에너지는 $\mathrm{\mid }$이다. 따라서 그룹 부터 까지를 하나의 부분으로 묶는 비용은 다음과 같다.

$$C(l,r)=\sum_{l\le i<j\le r}w_iw_j(j-i).$$

원래 트리에서 그룹을 구할 때는 $A$를 루트로 잡아 부모와 부모가 먼저 등장하는 순회 순서를 만든다. $Z$에서 부모를 따라가면 코어 경로를 얻는다. 경로 정점들의 그룹 번호를 먼저 표시한 다음, 순회 순서대로 경로 밖 정점에 부모의 그룹 번호를 물려주면 된다. 이 과정은 $O(N)$ 시간이다.

2. 구간 비용을 $O(1)$에 계산하기

다음 누적합을 정의하고, 인덱스 0의 값은 모두 0으로 둔다.

$$W_i=\sum_{j=1}^{i}w_j,\qquad P_i=\sum_{j=1}^{i}j w_j,\qquad H_i=C(1,i).$$

새 그룹 $i$와 이전 그룹들 사이의 비용만 더하면 되므로 $H_i$는 다음 식으로 계산할 수 있다.

$$H_i=H_{i-1}+w_i(iW_{i-1}-P_{i-1}).$$

$t=l-1$이라 하자. $H_r-H_t$에는 구간 내부의 비용뿐 아니라 와 사이의 비용도 포함된다. 뒤의 비용을 빼면 다음 식을 얻는다.

$$C(l,r)=H_r-H_t-W_t(P_r-P_t)+P_t(W_r-W_t).$$

세 누적합을 $O(M)$에 구한 뒤에는 구간 비용을 $O(1)$에 계산할 수 있다.

3. 동적 계획법

$DP_k[r]$를 처음 $r$개의 그룹을 정확히 $k$개의 비어 있지 않은 연속 구간으로 나누는 최소 비용이라고 하자. 마지막 구간이 $[l,r]$인 경우를 모두 고려하면 다음 점화식을 얻는다.

$$DP_k[r]=\min_{k\le l\le r}\{DP_{k-1}[l-1]+C(l,r)\}.$$

초기값은 $DP_0[0]=0$이며, 만들 수 없는 상태는 무한대로 둔다. 최종 답은 $DP_K[M]$이다. 이 점화식을 그대로 계산하면 시간이 필요하다.

4. Monge 성질과 분할 정복 최적화

$a\le b\le c\le d$일 때 다음 차이를 전개하자.

$$C(a,d)+C(b,c)-C(a,c)-C(b,d)=\sum_{i=a}^{b-1}\sum_{j=c+1}^{d}w_iw_j(j-i)\ge0.$$

즉, 구간 비용은 Monge 부등식을 만족한다. 후보 $l$마다 $DP_{k-1}[l-1]$을 더해도 이 부등식은 유지된다. 이 때문에 $r$이 증가할 때 최적인 마지막 구간의 시작점이 왼쪽으로 이동하지 않는다. 동률에서는 가장 작은 시작점을 고르면 이러한 단조성을 일관되게 유지할 수 있다.

한 $DP$ 층을 계산할 때 $r$의 중간값 $mid$를 먼저 처리한다. 가능한 최적 시작점의 범위가 $[L,R]$이라면 $l$을 $$부터 까지 검사하여 최적인 위치 를 찾는다. 이후 왼쪽 절반에서는 후보 범위를 로, 오른쪽 절반에서는 로 좁혀 재귀적으로 계산한다. 번째 층의 처음 호출은 의 범위 , 후보 범위 에서 시작한다. 이전 층의 불가능한 상태는 후보에서 제외한다.

재귀 깊이는 $O(\log M)$이고 한 깊이에서 검사하는 후보 수의 합이 $O(M)$이므로, 한 층을 $O(M\log M)$에 계산할 수 있다.

5. 복잡도와 구현 시 주의할 점

전체 시간복잡도는 $O(N+KM\log M)$, 공간복잡도는 $O(N)$이다. $DP$는 이전 층과 현재 층만 저장하면 된다.

정점 쌍은 $N(N-1)/2$개 이하이고 한 쌍의 에너지는 $M-1$ 이하이므로, 전체 에너지는 $4\times10^{15}$보다 작다. 또한 , 이므로 이다. 비용식에서 이 값들을 더하고 빼는 중간 계산도 64비트 정수 범위에 들어간다. 따라서 , , , , 값과 곱셈의 중간값을 모두 64비트 정수로 처리하면 된다. 가중치가 없는 원래 트리에서도 정답을 32비트 정수에 저장하면 안 된다.

트리가 길이 $N$인 경로일 수 있으므로 그룹을 구하는 트리 순회는 반복형으로 구현하면 깊은 재귀로 인한 스택 문제를 피할 수 있다. 분할 정복 $DP$의 재귀 깊이는 $O(\log M)$이다.