Tree Optimization

많은 Tree DP 문제들의 경우, 각 노드에서 특정 시간 복잡도로 노드들을 합치는 작업을 한다.

일반성을 잃지 않고, 노드의 자식이 3개 이상이라면, 더미 노드를 부모 쪽으로 계속 만들어 주며, 모든 트리를 이진 트리 형태로 변형시킬 수 있다. 따라서, 이진 트리에서 자식 노드 두개의 값만을 합쳐주는 문제로 생각한다.

 

1. $A$, $B$를 합치기 위해서 $sz(A) \cdot sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(N^2)$에 합칠 수 있다. (KOI18 검은 돌)

$sz(A) \cdot sz(B)$의 값은 왼쪽 자식의 서브트리의 모든 노드와 오른쪽 자식의 모든 서브트리의 노드를 연결했을 때 간선의 수와 같다. 이 때 어떠한 두 정점 $u$, $v$가 합쳐지는 위치는 바로 그 노드의 LCA $w$에서 합쳐지게 된다. 즉, 전체 각 노드별 $sz(A) \cdot sz(B)$의 합은 트리에서 임의의 두 노드를 선택하는 경우의 수와 같으니 $O(N^2)$이다.

 

2. $A$, $B$를 합치기 위해서 $min(K, sz(A)) \cdot min(K, sz(B))$의 시간이 필요할 때, 전체 시간복잡도 $O(NK)$에 합칠 수 있다.

1과 같은 논리로 두 노드 $u$, $v$가 합쳐지는 LCA $w$를 생각하자. $min(K, sz(A))$으로 인해 왼쪽 서브트리에서는 dfs ordering 순으로 큰 순서대로 $K$개, $min(K, sz(B))$으로 인해 오른쪽 서브트리에서는 dfs ordering 순으로 작은 순서대로 $K$개를 선택해 이어주는 경우의 수와 같다. 이는 전체 정점들을 dfs ordering 순으로 나열한 후 거리가 $2K$이하인 두 정점의 경우의 수와 같으니 $O(NK)$이다.

 

3. $A$, $B$를 합치기 위해서 $min(sz(A), sz(B))$의 시간이 필요할 때, 전체 시간복잡도 $O(NlogN)$에 합칠 수 있다. (Small to Large)

집합에서 더 크기가 작은 집합을 큰 집합쪽에 합쳐주는 과정을 반복할 때 어떤 원소 $u$가 다른 집합으로 옮겨가기 위해서는 집합의 크기가 2배 이상으로 커져야 한다. 즉, 모든 원소가 새로운 집합으로 옮겨가는 횟수가 $O(logN)$이니, 전체 시간복잡도는 $O(NlogN)$이다.

 

4. 트리가 일직선이거나, 성게일 때 $A$, $B$를 합치기 위해서 $sz(A)+sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(NlogN)$에 합칠 수 있다. (Divide & Conquer)

전체 노드에 대한 segment tree를 구성하면 각 노드의 구간마다 합치는데 그 노드의 범위만큼 걸린다. 일반적인 merge sort tree의 시간복잡도 분석과 같은 이유로, 전체 층의 개수가 $O(logN)$개이니, 전체 시간복잡도는 $O(NlogN)$이다.

 

5. $A$, $B$를 합치기 위해서 $sz(A)+sz(B)$의 시간이 필요할 때, 전체 시간복잡도 $O(Nlog^2N)$에 합칠 수 있다. (JOIOC18 Catdog)

트리에서 HLD를 하여, 모든 간선을 Heavy edge와 Light edge로 구분한다. 그 후, Heavy edge로 구성된 chain에 대한 segment tree를 구성한다. 이제, 전체 문제를 풀기 위해서는 루트를 포함하는 체인에서 각 노드마다 Heavy edge를 제외한 Light edge로 쪼개지는 서브트리에 대해서 재귀적으로 먼저 문제를 해결한다. 이제, 이 체인에 대한 문제는 다음 과정으로 해결한다.

1. 각 노드의 Light edge의 값들을 위 4의 성게일 때 DNC를 이용하여 합쳐 준다. $O(Nlog^2N)$

2. 합친 각 노드에 대해서 체인의 문제를 위 4의 일직선일 때 DNC를 이용하여 합쳐 준다. $O(Nlog^2N)$

각 노드에 대해 Heavy edge를 제외한 Light edge의 서브트리의 크기의 합은 $O(NlogN)$이니, 이에 DNC의 $O(logN)$이 붙어 전체 시간 복잡도 $O(Nlog^2N)$이다.