문제: 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값을 만족하는지를 판단하면 됩니다.
문제: 간선 하나를 잘라서 크기 x인 연결성분을 만들 수 있는지에 대한 여부가 1이상 n이하인 x에 대해 주어진다. 이 조건을 만족하는 트리가 있으면 아무거나 하나 출력하고, 없으면 -1을 출력하여라.
풀이: 또 다른 트리 복구 문제입니다. 몇몇 자명한 조건들을 살펴봅시다. 일단 간선 하나를 끊었을 때, 하나의 크기가 x이면 다른 하나의 크기는 n-x입니다. 그래서 si가 0인데, sn-i가 1인 경우에 (혹은 sn이 1인 경우에) 우리는 트리가 불가능하다고 말해주면 됩니다. 다른 자명하지만 중요한 조건을 하나 살펴봅시다. 트리에는 항상 리프가 존재하므로, 리프와 부모를 잇는 간선을 자른 경우에는 크기 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, ..., dm의 막대가 붙어있는 형태이다. (d는 양의 정수이다.) 각 막대 사이에는 관절이 있어서, 각 막대는 상하좌우중 아무 방향으로나 움직일 수 있다. 로봇 팔의 가장 마지막 부분이 주어진 좌표평면 N개의 점을 지나도록 로봇 팔을 구성할 수 있는가? (m ~ 40, N ~ 1000, d ~ 10^9)
풀이: 일단 진정하고 문제를 1차원에서 먼저 풀어봅시다. 로봇 팔은 L과 R밖에 없으며, 모든 점은 다 x축 위에 있습니다.
이 문제는 결국 +-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축에 대해 따로따로 풀어주면 됩니다.
