Merry Problem Solving 4일차
문제: i번째 정점부터, 다른 모든 정점까지의 거리의 합이 Di인 트리가 있으면 아무거나 출력하고, 없으면 -1을 출력하라. 단, Di는 모두 다르다.
풀이: 먼저 문제의 Special Judge를 생각해봅시다. 모든 i에 대한 Di를 어떻게 구하면 좋을까요? 일단, D1을 1번에서 dfs를 돌린 후에 모든 높이의 합으로 구할 수 있습니다. 이제 다른 모든 Di를 구해야 하는데, 하나의 Di를 구하면 다른 Di를 구할 수 있습니다. 이는 다음의 정리를 이용합니다.
정리. T(u)를 u까지의 거리가 v까지의 거리가 더 짧은 정점의 집합이라고 정의하고, T(v)에 대해서도 마찬가지로 정의하자. u와 v가 간선으로 연결되어 있을 때, Du+|T(u)| = Dv+|T(v)|이다.
증명.
x를 T(u)의 원소라고 합시다. x와 v의 경로는 u를 지나므로, d(x, u) + d(u, v) = d(x, v)입니다. 마찬가지로, y를 T(v)의 원소라고 하면, y와 u의 경로는 v를 지나므로, d(y, v) + d(v, u) = d(y, u)입니다.
d(u, v) = 1이므로, |T(u)|개의 수에 대해서는, d(x, u) + 1 = d(x, v)이고, |T(v)|개의 수에 대해서는, d(x, u) = d(x, v) + 1입니다. 모든 x에 대해 식을 전부 더해줄 경우에, Du + |T(u)| = Dv + |T(v)|가 나오게 됩니다.
그렇기 때문에, 우리는 어떤 노드 u와 그 부모 p에 대해서, Du + |T(u)| = Dp + |T(p)| = Dp + N - |T(u)|. 정리하면, Dp = Du + 2|T(u)| - N 이라는 사실을 얻어 낼 수 있고, 루트 부터 시작해서, 모든 트리의 정점들의 D값을 알 수 있습니다.
이제 복구를 시작해 봅시다. 일반성을 잃지 않고 D1 < D2 < ... < DN 이라고 가정합시다. 제가 처음으로 접근한 방법은 centroid를 먼저 루트로 잡는 것이었습니다. centroid는 Di 가 제일 작은 수이기 때문에 D1을 루트로 잡을 수 있습니다. centroid에서 루트를 제외한 subtree의 크기는 모두 N/2이하이기 때문에, 자식의 Di가 부모의 Di보다 무조건 작음을 알 수 있습니다. 그래서 두번째로 큰 수는, 루트의 자식이 되어야 하고, subtree의 크기를 결정할 수 있습니다. 세번째로 큰 수 까지는 어떻게 결정할 수 있는데, 네번째로 큰 수가 복구가 쉽게 되지 않습니다. 왜냐하면 트리에 붙을 수 있는 방법이 두가지 이상이 되어버리기 때문입니다.
그래서 이 아이디어를 그대로 이용하여, 리프부터 복구를 시작했습니다. x를 N부터 1까지 차례대로 내려오면서 x의 부모노드를 구합시다. (1번 정점은 centroid이고, 루트입니다.) x번째 노드의 D값이 Dx이면, 그 부모 노드 p에 대해서는, Dp = Dx + 2|T(x)|-N 입니다. D값이 모두 다르기 때문에, p가 유일하게 정해집니다. |T(x)|는, 정점 x보다 Dx 큰값에 대해 부모가 모두 정해져 있기 때문에 바뀌지 않습니다. 이렇게 p를 정하면 p가 x의 부모로 정해지게 됩니다. (구현시에는, T(p)의 값을 T(p) + T(x)로 업데이트 합니다.)
그래서, 우리는 이 방식으로 부모를 계속 구하고, 트리를 복구한 후에, 복구 한 트리가 실제로 D값을 만족하는지를 판단하면 됩니다.
ARC103E - Tr/ee
다른 자명하지만 중요한 조건을 하나 살펴봅시다. 트리에는 항상 리프가 존재하므로, 리프와 부모를 잇는 간선을 자른 경우에는 크기 1인 연결성분이 생기고, s1은 무조건 1이어야 합니다.
이렇게 s에 대한 기본적인 체크를 한 이후에, 우리는 s를 만들어 볼 것입니다. 또, 트리의 루트는 아무거나 잡으면 되기 때문에 centroid를 잡을 것 입니다. centroid를 트리의 루트로 잡으면 루트를 제외한 subtree의 크기는 모두 N/2이하입니다. 그래서 우리는 주어진 1이상 N/2이하의 숫자들에 대해서, subtree의 크기가 정확히 주어진 수가 되도록 만들면 됩니다.
만드는 한 가지의 방법은 다음과 같습니다. 주어진 수들을 1 < a1 < a2 < ... < aK 라고 합시다. 일단, 가장 큰 수인 aK가 subtree의 크기인 노드는 바로 자식이어야 될 것 입니다. 나머지 N-aK의 노드들은 어떻게 할까요? 우리는 루트에다가 N-aK개의 리프를 붙일 것 입니다. 이 정점들의 subtree의 크기는 1이고, 다른 풀이에 영향을 주지 않습니다.
이제 aK가 subtree의 크기인 노드에서, aK-1이 subtree의 크기인 노드를 만들어야 합니다. 나머지 선택지는 없으니, 자식으로 붙여주고, 나머지 aK-aK-1개의 노드들을 리프로 붙여줍시다.
이와 같은 방법으로 만들면, 문제의 조건을 만족하는 경로 하나가 있고, 리프가 마구 붙은 형태의 트리를 만들 수 있습니다.
이 문제는 결국 +-d1+-d2+-d3+-...+-dm 으로 정해진 수를 모두 만들 수 있게 하라는 질문과 같습니다. -d1-d2-d3-...-dm 부터 생각해 보았을 때, di의 부호를 -에서 +로 바꾸는 것은 결국엔 2di를 더하는 것과 같습니다.
결론적으로, (+-1)+-1+-2+-4+-...+-2k와 같이 숫자를 정하게 될 경우에, -d1-d2-d3-...-dm 으로 부터, 정해진 위치인 x까지 더해야 할 수 x+d1+d2+...+dm 을 2진법으로 표현하는 문제가 됩니다. 홀짝에 따라 처음 1은 포함되어야 할 수도 있고 아닐수도 있습니다.
이제 이 문제를 2차원에서 풀어야 합니다. 이것은 좌표평면을 45도 돌리면 가능합니다. L, R, D, U가 (x+y, x-y) -> (x+y+-2d, x-y+-2d) 에 대응되기 때문에, 문제를 x+y축과 x-y축에 대해 따로따로 풀어주면 됩니다.