1634번 - 완전 이진트리

‘k-레벨 완전 이진 트리’는 모든 노드의 분지수(차수)가 0이거나 혹은 2이고, 레벨 1에 있는 노드 수가 2^0, 레벨 2에 있는 노드수가 2^1, ... , 레벨 k에 있는 노드 수가 2^(k-1)이며, 총 노드 수는 2^k-1인 이진 트리를 말한다. 두 개의 k-레벨 완전 이진 트리 T1과 T2가 있고, 각 트리의 단말 노드들, 즉 레벨 k의 노드들에 대하여 L={1,2,...,N}에 속하는 서로 다른 정수들이 할당되어 있다. 다음 조건을 만족하는 L의 부분 집합 s를 찾는 프로그램을 작성하시오.

• S에 속하는 모든 쌍의 정수 x, y에 대하여 T1과 T2에서 x가 할당된 노드와 y가 할당된 노드 사이의 거리가 서로 같다. 두 노드 사이의 거리는 두 노드를 잇는 경로가 지나는 에지의 수이다.
• S에 속한 원소의 수는 반드시 최대이어야 한다.

왼쪽 그림이 T1, 오른쪽 그림이 T2이다.

예를 들어, k = 4인 경우에 아래 그림과 같이 단말 노드에 정수가 할당된 두 트리 T1과 T2가 주어져 있다고 하자. 두 트리 T1과 T2의 단말 노드들에 할당된 수들을 왼쪽에서 오른쪽으로 차례대로 쓴 것이 각각 (4, 2, 1, 3, 6, 7, 5, 8)과 (2, 7, 4, 8, 3, 1, 6, 5)라고 하자. 이 경우에 구하고자 하는 답은 S = {1, 3, 7, 8}이다. 예를 들어, S에 속하는 한 쌍의 정수 3, 7에 대하여 T1과 T2에서 3이 할당된 노드와 7이 할당된 노드 사이의 거리가 6으로 서로 같다.

첫줄에 두 트리 T1과 T2의 레벨 k (1<=k<=12)가 주어진다. 둘째 줄에 T1의 단말 노드들에 할당된 수들이 왼쪽에서 오른쪽으로 차례로 주어진다. 셋째 줄에 T2의 단말 노드들에 할당된 수들이 왼쪽에서 오른쪽으로 차례로 주어진다.

첫 줄에 주어진 조건을 만족하는 최대 집합 에 속하는 원소의 수를 출력한다.