BOJ 24634 Развитие города
문제 내용
노드가 개인 트리가 주어집니다. 이 트리의 루트는 1번 노드입니다. 이 트리에 원래 트리의 일부분을 복사하여 붙이려고 합니다.
구체적으로, f t라는 쿼리가 주어지면, 원래 트리에서 번 노드를 루트로 하는 서브트리를 복사하여 그 루트를 노드 의 새로운 자식으로 만듭니다.
이때 복사본의 각 노드의 번호는 원래의 서브트리에서 노드 번호가 증가하는 순으로 새로운 번호로 매겨집니다. 해당 쿼리는 개가 주어집니다.
복사-붙여넣기 쿼리가 완료된 뒤에, 개의 노드 쌍에 대해 두 노드 사이의 거리를 구하세요.
입력
첫 줄에 , , 의 값이 주어집니다. ()
다음 줄에 원래 트리의 간선이 주어집니다. a b는 번 노드와 번 노드가 연결되었다는 뜻입니다.
그다음 줄에 복사-붙여넣기 쿼리 f t가 주어집니다. (, , 는 해당 쿼리 직전의 총 노드의 개수 이하)
마지막 줄에 거리를 계산할 노드의 쌍들이 주어집니다. (각 노드 번호는 1 이상 총 노드 개수 이하)
출력
각각의 거리 쿼리에 대해 두 노드 간의 거리를 한 줄에 하나씩 출력합니다.
문제 풀이
스포일러
모든 쿼리가 종료되었을 때의 전체 트리를 시간 내에 만들 수 없으므로, 복붙 쿼리로 추가되는 노드의 집합을 하나의 노드("메가노드")로 하는 별도의 트리("메가트리")를 만듭니다.
각각의 노드가 몇 번 메가노드에 속하는지는 각 메가노드에 속한 노드 번호의 범위를 순차적으로 저장해 놓고 이분탐색을 하는 것으로 알아낼 수 있습니다.
그 노드가 원래 트리에서 몇 번 노드인지를 알아내려면, 서브트리에서 번째로 작은 수 쿼리를 처리할 수 있어야 합니다. 이는 ETT 배열에 머지 소트 트리, PST, 또는 PBS를 사용하여 구할 수 있습니다. (머지 소트 트리를 사용할 경우 알려진 방법은 쿼리당 이 걸리지만 상수가 작다고 알려져 있으나, 이 문제에서는 별도의 상수 최적화를 하지 않으면 TLE를 받을 수 있습니다.)
이제 원래 트리의 각 노드의 depth를 미리 계산해 놓으면 각각의 메가노드 내의 루트의 depth도 알 수 있고, 원래 트리와 메가트리에서 LCA를 구하는 알고리즘을 써서 임의의 두 노드 사이의 거리를 구할 수 있습니다.