10008 Polarization

정점 수가 $N$인 트리가 주어진다. 간선에 방향을 부여해 이동할 수 있는 정점 쌍의 수를 최대화하라.

사실 최솟값도 구해야하지만 쉽게 $N-1$임을 알 수 있으므로 생략했습니다.

 

 

 

 

---

 

 

 

 

 

 

간선의 방향은 어떤 정점 $r$을 기준으로 어떤 서브트리는 내려가는 방향, 어떤 서브트리는 올라오는 방향으로 하는 것이 최적이다.

 

증명은 만약 아니라면, 간선의 방향을 바꾸어 증가시킬 수 있다는 것으로 충분합니다.

이제 그러면 $r$을 중심으로 나머지 서브트리를 최대한 잘 반띵하는 것이 목표가 됩니다.

과연 어떤 정점 $r$을 잡는 것이 이득일까요?

 

$r = cent$일 때 최적해를 가진다

 

만약 사이즈가 $N/2$보다 큰 서브트리가 있다면, 그 방향으로 한 칸 움직이는 것으로 더욱 최적임을 알 수 있습니다.

 

그러면 이제 센트를 중심으로 나머지 서브트리들을 $N/2$에 최대한 가깝게 나누는 문제가 되었습니다. 이는 간단한 냅색으로 해결할 수 있습니다.

 

먼저 서브트리 내부는 DFS를 이용하면 $O(N)$에 값을 계산해 줄 수 있습니다.

같은 값이 여러개 나오는 경우는 $w/2, w/4 \dots$로 분리하는 방법을 통해 $logN$개로 바꿀 수 있습니다.

서로 다 값이 다르다 가정하면 가능한 값은 최대 $\sqrt{N}$개이므로, 총 시간복잡도 $N\sqrt{N}$에 문제를 풀 수 있습니다.