서브트리의 최소 길이합

현재 주요 정점들의 집합을 $S$라고 하자. $S$가 비어 있거나 원소가 하나뿐이면 답은 $0$이다.

트리를 $1$번 정점을 루트로 잡고 DFS를 한다. 정점 $v$의 DFS 방문 시각을 $tin[v]$라고 하자. $S$의 정점들을 $tin$이 증가하는 순서대로 $v_1,v_2,\ldots,v_k$라고 쓰고, $v_{k+1}=v_1$이라고 하자. 다음 값을 정의한다.

$$C(S)=\sum_{i=1}^{k} dist(v_i,v_{i+1})$$

이때 답은 $C(S)/2$이다.

이를 보이자. $S$의 모든 정점을 포함하는 최소 연결 부분트리를 $T_S$라고 하자. $T_S$의 임의의 간선 $e$를 제거하면 $T_S$는 두 컴포넌트로 나뉘며, 양쪽 컴포넌트에는 각각 적어도 하나의 주요 정점이 있다. DFS 순서로 주요 정점들을 원형으로 나열하면 한쪽 컴포넌트에 있는 주요 정점들의 구간과 다른쪽 컴포넌트에 있는 주요 정점들의 구간 사이를 넘어가는 인접쌍이 정확히 두 번 생긴다. 따라서 $C(S)$에서 간선 $e$의 길이는 정확히 두 번 더해진다. 모든 간선에 대해 같은 논리가 성립하므로 $C(S)=2\sum_{e\in T_S}w(e)$이고, 답은 $C(S)/2$이다.

이제 현재 주요 정점들을 $tin$ 순서의 ordered set으로 관리하고, 현재 $C(S)$ 값을 64비트 정수 변수로 유지한다.

정점 $x$를 추가한다고 하자. 현재 집합이 비어 있지 않다면, 원형 $tin$ 순서에서 $x$의 바로 이전 정점을 $p$, 바로 다음 정점을 $n$이라고 하자. 기존에는 $p$와 $n$이 인접해 있었으므로 $dist(p,n)$이 더해져 있었다. $x$를 추가하면 이 항이 사라지고 $dist(p,x)$와 $dist(x,n)$이 생기므로 다음과 같이 갱신한다.

$$C\leftarrow C+dist(p,x)+dist(x,n)-dist(p,n)$$

정점 $x$를 제거할 때는 반대로 다음 갱신을 적용한다.

$$C\leftarrow C-dist(p,x)-dist(x,n)+dist(p,n)$$

집합의 크기가 $0$ 또는 $1$인 경우에는 $C=0$으로 처리하면 된다.

거리 $dist(u,v)$는 LCA 전처리로 구한다. 루트에서 정점 $v$까지의 거리를 $D[v]$라고 하면 다음 식을 사용한다.

$$dist(u,v)=D[u]+D[v]-2D[lca(u,v)]$$

LCA 전처리에 $O(N\log N)$ 시간이 걸린다. 각 사건마다 ordered set 연산과 LCA 거리 계산을 상수 번 수행하므로 $O(\log N)$ 시간에 처리된다. 전체 시간복잡도는 $O((N+Q)\log N)$이고, 메모리복잡도는 $O(N\log N)$이다.

Solution written by GPT5.5