RUN@KAIST 7/12 방학 연습 풀이

1. ČVENK

점 (x, y)가 빈 공간이기 위해서는 x & y = 0이 성립해야 한다. 이 점에서는 항상 (0, 0)으로 가는 경로가 존재하는데, 다음과 같은 방법으로 이를 찾을 수 있다.

 * x == 0 || y == 0일 경우에는 자명하게 경로를 찾을 수 있다.

 * x와 y가 모두 0이 아니라고 가정하자. lowest significant bit (LSB) 가 작은 쪽을 찾자. 여기서는 일반성을 잃지 않고 x라고 한다. 그렇다면, (x - LSB(x), y) - (x, y) 를 잇는 경로는 비어 있다. (x - LSB(x), y) 에서 재귀적으로 계속 경로를 찾아나간다.

이 경로는 항상 존재하며 유일하다. 이는 빈 공간들이 트리를 이룬다는 증명이 되기도 한다. (사실 그건 사진을 보면 쉽게 눈치챌 수 있지만..)

이 사실을 사용하면, 10^9 * 10^9 격자를 모두 트리로 만들 필요가 없다. 주어진 n개의 점에 대해서 저러한 경로는 많아야 32개의 서로 다른 점들을 가진다. 고로, 그 32 * N개의 점을 가지고 트리를 만들면 해당 구조를 그대로 표현할 수 있다. 트리를 만드는 방법은, 정점들을 모두 정렬한 후, LSB가 작은 쪽이 x인지 y인지에 따라서, 해당 방향으로 제일 먼저 닿는 점에 에지를 이어주는 식으로 할 수 있다.

이러한 방법으로 트리를 만들었다면, 이제 모든 사람들이 모이는 최적의 점을 찾으면 된다. 이를 찾는 방법은 다음과 같다. 루트부터 시작해서, 만약에 현재 자식 중 서브트리에 N/2명 이상이 있다면, 해당 자식쪽에 최적점을 두는 것이 이득이다. 이를 반복하면, 서브트리에 N/2명 이상이 없는 상황이 존재하게 될 것이다. 이 경우에는, 어떠한 자식으로 들어가도 손해를 본다. 고로, 해당 점을 최적점이라 두자. 이 방법을 사용하면 루트에서 단순히 내려가면서 최적 위치를 찾을 수 있으며, 또한 이 알고리즘은 에지 상에 최적 점이 없다는 증명이 되기도 한다. 트리의 Centroid를 아는 사람들에게는 아주 익숙한 개념일 것이다. 

이제 최적 위치를 구했으니, 해당 위치에서 dfs를 통해서 답을 구할 수 있다.

2. 단말 정점들의 거리

이진 트리의 단말 정점들의 거리를 알고 있으면, 거리 뿐만 아니라 이진 트리 전체를 복원할 수 있다. 트리를 복원했으면 거리를 구하는 것은 쉬울 것이니, 이 방법을 알아보자.

N개의 단말 정점들의 거리가 주어지면, 두 단말 정점 간의 거리가 2인 경우가 항상 존재한다. (아니라고 해보자!) 이 경우, 두 단말 정점은 공통된 조상 하나를 가진다는 것을 알 수 있다. 두 단말 정점을 공통된 조상 하나로 묶어주고, 그 공통된 조상 하나를 다시 단말 정점이라고 두자. 공통된 조상의 양 옆 거리를 갱신해주고 (원래 거리 - 1이다.), N-1개의 단말 정점들의 거리로 트리를 만들어주면 된다. 이와 같은 귀납적인 방법으로 트리를 만들 수 있다.

3. 배럭

링크로 대체