ARC 103 F. Distance Sums

https://beta.atcoder.jp/contests/arc103/tasks/arc103_d

일단 일반성을 잃지 않고 $D_1 < D_2 < \cdots < D_N$ 을 만족하게 정렬할 수 있다. 그러면 결국 1번 노드는 centroid가 되고, 1번 노드를 루트로 하였을 때 $i > 1$ 번 노드의 부모는 $i$번 보다 작은 번호를 가진다. 이 부분의 증명은 생략한다. Centroid의 성질을 생각해 보면 그렇게 어렵지 않다.

고로 루트 (centroid) 를 기준으로 하나 하나 노드를 붙여나가는 식의 풀이가 될 것이라고 생각할 수 있으나, 생각처럼 잘 안된다. 어떠한 노드를 추가할 때 무슨 노드를 부모로 삼을 지가 명확하지 않다.

여기서 발상을 전환시켜서, 위 과정을 반대 방향으로 해 보자. $N$번 노드의 부모를 알고 싶다고 해 보자. $N$ 번 노드는 자명히 리프이니, $N$ 번 노드의 부모가 될 노드는 $D_j = D_N - (N - 2)$ 를 만족한다. 모든 $D_i$ 가 서로 다르기 때문에 이를 만족하는 $j$는 유일하다! 고로 $N$번 노드의 부모를 알 수 있다. 

일반적으로, $i$번 노드의 부모는 $D_j = D_i - N + 2 * sub(i)$ 를 만족한다. 이 때 $sub(i)$ 는 $i$번 노드를 루트로 한 서브트리의 크기이다. $N$에서 $i+1$까지 순서대로 부모를 찾았다고 하면 $sub(i)$ 를 쉽게 알 수 있다. 고로 $D_j$ 를 알 수 있고, 임의의 $i$번 노드의 부모를 알 수 있다.

답을 만족할 가능성이 있는 유일한 트리를 알아냈으니, 이제 검증을 하면 된다. 검증을 단순히 하면 $O(N^2)$ 이 되지만, 잘 생각해 보면 $D_{par(i)} = D_i - N + 2 * sub(i)$ 가 항상 만족하기 때문에, $D_{par(i)}$ 가 맞으면 $D_i$가 맞다. 고로 $D_1$ 이 맞는지만 검증해 주면 모든 답이 맞는다. 이는 단순 DFS로 $O(N)$ 에 판별 가능하다.