Evolution

[서브태스크 2] $M=83$ (74.27점)

$M=84$의 병목은 $k=6$에서 $939\,993$개의 순번을 고정 길이 $20$비트로 저장하는 부분이다.

라벨의 앞쪽 $0$은 의미가 있고, 라벨 길이 자체도 정보가 된다. 길이 $15,16,17,18,19$의 모든 비트열을 하나의 연속된 코드 공간으로 사용하면 $2^{15}+2^{16}+2^{17}+2^{18}+2^{19}=1\,015\,808$개의 값을 표현할 수 있다.

$k=6$의 나머지 필드는 $64$비트이므로 전체 길이는 $79$부터 $83$까지이다. 다른 $k$의 길이와 겹치지 않게 배치하면 밥은 전체 길이만 보고 $k$와 순번 부분의 길이를 함께 알아낼 수 있다.

여기까지는 DFS 구간의 경계와 작은 간선의 부모 번호를 직접 압축했다. 이제는 저장할 정보를 더 잘 줄이는 대신, 정점의 경로를 표현하는 방법 자체를 바꾼다.

[서브태스크 2] $M=51$ (94.09점)

지금까지의 풀이는 DFS 순서, 서브트리의 양 끝, 몇몇 조상의 번호를 라벨에 직접 저장했다. 이 방식은 이해하기 쉽지만, 필요한 조상 수가 늘어나면 정점 번호만으로도 많은 비트가 필요하다.

$M=51$부터는 관점을 완전히 바꾼다. 실제 트리의 정보를 하나씩 저장하는 대신, 앨리스와 밥이 실험 전에 같은 라벨 해석용 설계도를 미리 만든다. 앨리스는 입력 트리를 이 설계도 안에 배치하고, 밥은 라벨 두 개가 설계도 안에서 어떻게 갈라지는지만 따라간다.

공통 설계도 $U_n$이 뜻하는 것

$U_n$은 실제 입력 트리 한 그루가 아니다. 정점이 최대 $n$개인 어떤 루트 트리가 주어져도, 그 트리의 정점들을 배치할 수 있도록 미리 만들어 둔 공통 설계도이다.

여기서 "배치한다"는 말은 다음 뜻이다.

• 입력 트리의 각 정점은 설계도 안의 한 위치에 대응된다.
• 입력 트리에서 어떤 정점 $x$가 $y$의 조상이면, $y$의 위치로 내려가는 과정에서 $x$의 위치를 먼저 지난다.
• 두 정점 $u,v$의 LCA가 $x$라면, 두 위치를 위에서부터 함께 따라갈 때 $x$까지는 같은 길을 가고, $x$에서 처음 서로 다른 자식 방향으로 갈라진다.

입력 트리의 간선 하나가 설계도에서도 반드시 간선 하나일 필요는 없다. 중간에 사용하지 않는 위치를 몇 개 지나갈 수 있다. 중요한 것은 조상 관계와 갈라지는 지점이 그대로 유지되는 것이다.

예를 들어 입력이 긴 경로라면 정점들을 설계도의 한 방향으로 계속 배치할 수 있어야 한다. 입력이 별 모양이라면 루트를 한 위치에 두고, 여러 잎을 서로 다른 자식 방향에 배치할 수 있어야 한다. $U_n$은 이 두 경우를 포함하여 정점 수가 $n$ 이하인 모든 모양을 받아 주는 하나의 공통 설계도이다.

$W(n)$을 $U_n$에서 사용할 수 있는 서로 다른 위치 번호의 개수라고 하자. 목표는 $W(256)$을 충분히 작게 만드는 것이다.

설계도의 한 분기점을 만드는 방법

입력 트리의 어떤 정점 $x$를 설계도의 현재 분기점에 배치했다고 하자. $x$의 원래 번호를 $c$라 하자.

현재 분기점에는 여러 자식 방향이 있다. 자식 방향 $i$ 아래에는 더 작은 트리를 받아 주는 설계도 $G_i$가 연결되어 있고, $G_i$의 위치 수를 $w_i$라 하자.

현재 분기점 아래의 위치는 다음 두 종류이다.

• 위치 번호 $0$: 현재 정점 $x$ 자체
• 자식 방향 $i$로 내려가는 위치: 그 방향에서 사용하는 기호와, $G_i$ 안의 위치 번호를 합친 것

방향 $i$에서 정점 번호 $c$에 대응하여 사용할 기호를 $f_i(c)$라 하자. 밥이 서로 다른 두 자식 방향 $i,j$에서 나온 기호 $f_i(c),f_j(c)$를 보면 $c$를 유일하게 알아낼 수 있도록 기호를 정한다.

이 조건이 왜 필요한지 보자. 두 질의 정점이 현재 정점 $x$의 서로 다른 자식 서브트리에 있다면, 두 라벨은 현재 분기점에서 서로 다른 방향으로 갈라진다. 이때 밥은 두 기호만 보고 현재 정점의 번호 $c$, 즉 LCA의 번호를 반환해야 한다.

반대로 두 라벨의 기호가 같다면 같은 자식 방향으로 내려갔다는 뜻이어야 한다. 그러면 밥은 두 라벨의 나머지 부분을 $G_i$ 안에서 계속 비교하면 된다.

방향 $i$가 사용할 수 있는 기호의 수를 $a_i$라 하면, 이 분기점에서 필요한 전체 위치 수는 $1+\sum_i a_iw_i$이다. 기호 하나마다 $G_i$의 모든 위치가 한 묶음씩 필요하기 때문이다. 따라서 위치 수가 큰 자식 방향에는 가능한 한 작은 기호 집합을 주어야 한다.

자식이 하나 또는 둘일 때

자식이 하나뿐이면 구분할 다른 방향이 없다. 기호는 한 종류면 충분하고, 필요한 위치 수는 $1+w_0$이다.

자식이 둘이라면 $LR\geq256$을 만족하는 양의 정수 $L,R$을 고른다. 정점 번호 $c$를 첫 번째 방향에서는 $c\bmod L$, 두 번째 방향에서는 $\lfloor c/L\rfloor$로 저장한다.

두 값을 함께 알면 $c$를 복원할 수 있다. 필요한 위치 수는 $1+Lw_0+Rw_1$이다. 구현에서는 가능한 $L$을 모두 확인하여 이 값이 가장 작은 선택을 사용한다.

자식이 셋 이상일 때

가장 단순하게는 모든 방향에서 정점 번호 $c$를 그대로 저장할 수 있다. 그러면 각 방향에 $256$개의 기호가 필요하다. 항상 정확하지만 위치 수가 너무 커진다.

이를 줄이기 위해 구현에서는 다음 방법들을 비교한다.

첫 번째 방법은 $c$의 $8$개 비트를 방향별로 나누는 것이다. 각 방향은 일부 비트를 생략하고 나머지 비트만 저장한다. 서로 다른 두 방향이 생략하는 비트 집합을 겹치지 않게 하면, 두 방향이 저장한 비트를 합쳐 원래 $8$비트를 모두 복원할 수 있다. 위치 수가 큰 방향일수록 더 많은 비트를 생략하도록 정하면 비용을 줄일 수 있다.

두 번째 방법은 $c$를 두 작은 값 $u,v$로 나누는 것이다. $q=2^b$라 하고 $c=uq+v$로 둔다. $q$개의 값을 대상으로 덧셈과 곱셈을 할 수 있는 계산 규칙을 하나 미리 정한다. 각 자식 방향에는 $v+t u$ 꼴의 값을 저장한다. 서로 다른 두 $t$에 대한 값을 알면 두 식을 풀어 $u,v$를 복원할 수 있다. 한 방향에는 $u$ 자체를 저장할 수도 있다.

구현은 $b=4,5,\ldots,8$을 확인하고, 비트 생략 방식과 두 값으로 나누는 방식을 모두 비교한다. 각 방식에서 실제 비용 $1+\sum_i a_iw_i$가 가장 작은 것을 그 분기점의 규칙으로 선택한다.

중요한 점은 앨리스와 밥이 입력 트리와 관계없이 완전히 같은 규칙으로 이 선택을 계산한다는 것이다.

임의의 트리를 하나의 설계도에 넣는 방법

한 분기점의 표현 방법은 정했다. 이제 정점 수가 $n$ 이하인 모든 트리를 받아 주는 $U_n$을 만들어야 한다.

$0\leq m\leq\lfloor(n-1)/2\rfloor$인 $m$을 하나 고르고, $C=n-m$이라 하자. 그러면 $C>n/2$이다.

어떤 정점의 자식 중 서브트리 크기가 $C$ 이상인 자식은 많아야 하나이다. 두 개가 있다면 그 두 서브트리만 합쳐도 크기가 $2C>n$이 되어 불가능하기 때문이다.

따라서 입력 트리에서 크기가 $C$ 이상인 자식이 있으면 그 자식을 계속 따라갈 수 있다. 이렇게 얻는 경로를 중심 경로라고 하자. 중심 경로의 마지막 정점에는 크기가 $C$ 이상인 자식이 없다.

중심 경로의 마지막 정점을 제외한 각 정점에서, 현재 정점 하나와 중심 경로 밖으로 달린 모든 옆 서브트리의 크기 합을 차례로 $b_1,b_2,\ldots,b_t$라 하자.

중심 경로의 마지막 서브트리에는 적어도 $C$개의 정점이 남아 있다. 따라서 그 밖에 있는 정점 수는 최대 $n-C=m$이고, $\sum_i b_i\leq m$이다.

이제 문제는 다음과 같이 바뀐다.

예를 들어 $A_5=(2,1,5,2,1)$이다.

이 수열은 다음 성질을 가진다. 양의 정수열 $b_1,b_2,\ldots,b_t$의 합이 $m$ 이하라면, $A_m$에서 순서를 유지하며 값 $a_1,a_2,\ldots,a_t$를 골라 모든 $i$에 대해 $b_i\leq a_i$가 되게 할 수 있다.

증명은 가운데의 $m$을 기준으로 나누면 된다. $\ell=\lfloor(m-1)/2\rfloor$라 하자. $b$의 누적합이 처음으로 $\ell$을 넘는 항을 가운데 값 $m$에 대응시킨다. 그 앞부분의 합은 $\ell$ 이하이므로 왼쪽의 $A_\ell$이 받아 줄 수 있다. 그 뒷부분의 합은 $\lceil(m-1)/2\rceil$ 이하이므로 오른쪽 수열이 받아 줄 수 있다. 양쪽에서 같은 논리를 반복한다.

따라서 중심 경로의 각 $b_i$를 $A_m$의 어떤 값 $a_i$에 순서대로 배정할 수 있다. $A_m$에서 선택되지 않은 위치는 실제 입력 정점과 대응시키지 않고, 중심 경로가 지나가기만 하는 빈 위치로 둔다.

한 중심 경로 위치에 필요한 옆 공간

어떤 중심 경로 정점이 값 $a$에 배정되었다고 하자. 이 정점의 옆 자식 서브트리 크기를 큰 순서대로 $s_1\geq s_2\geq\cdots$라 하자.

현재 정점 하나를 제외한 옆 서브트리 크기의 합은 $a-1$ 이하이다. 따라서 $r$번째로 큰 옆 서브트리는 $s_r\leq\lfloor(a-1)/r\rfloor$을 만족한다. 그렇지 않다면 앞의 $r$개 서브트리 크기 합이 $a-1$보다 커진다.

그러므로 값 $a$에 대응하는 설계도 위치에는 다음 자식 방향들을 준비하면 충분하다.

• 중심 경로가 계속 이어지는 방향
• 크기 $a-1$ 이하의 트리를 받는 방향
• 크기 $\lfloor(a-1)/2\rfloor$ 이하의 트리를 받는 방향
• 크기 $\lfloor(a-1)/3\rfloor$ 이하의 트리를 받는 방향
• 그 뒤 같은 방식으로 필요한 방향들

중심 경로의 마지막 정점에서는 크기가 $C$ 이상인 자식이 없다. 따라서 가장 큰 자식은 크기 $C-1$ 이하이다. 모든 자식의 전체 크기 합은 $n-1$이므로, 크기 순서로 $r$번째 자식은 $\lfloor(n-1)/r\rfloor$ 이하이다. 마지막 위치에도 이 상한에 맞는 자식 방향들을 준비하면 된다.

각 자식 방향에는 더 작은 크기의 공통 설계도 $U_s$를 붙인다. 모든 $s<n$이므로 같은 구성을 작은 크기부터 차례로 만들 수 있다.

이제 앞에서 사용한 문장을 정확히 해석할 수 있다. "모든 트리를 $U_n$에 넣는다"는 것은 입력 트리에서 중심 경로를 찾고, 그 경로의 정점들을 $A_m$의 일부 위치에 배치하고, 옆 서브트리들을 크기 순서에 맞는 더 작은 $U_s$에 다시 배치하는 과정을 반복한다는 뜻이다.

$W(n)$을 계산하는 DP

$W(0)=0$, $W(1)=1$로 둔다. $n\geq2$에서는 가능한 모든 $m$을 시험한다.

먼저 중심 경로의 마지막 위치를 만든다. 그 자식들이 받아야 하는 최대 크기는 $C-1,\lfloor(n-1)/2\rfloor,\lfloor(n-1)/3\rfloor,\ldots$이다. 각 크기 $s$를 이미 계산한 위치 수 $W(s)$로 바꾸고, 앞의 기호 설계 방법으로 이 분기점의 전체 위치 수를 계산한다.

그 다음 $A_m$을 뒤에서부터 확인한다. 값 $a$에 해당하는 위치를 하나 추가할 때는, 지금까지 만든 중심 경로의 나머지 부분을 받는 방향 하나와 크기 $a-1,\lfloor(a-1)/2\rfloor,\ldots$를 받는 옆 방향들을 한 분기점에 연결한다.

이렇게 모든 위치를 붙인 뒤의 위치 수가, 해당 $m$을 사용했을 때의 $U_n$ 크기이다. 모든 $m$ 중 가장 작은 값을 $W(n)$으로 정한다.

DP에는 숫자만 저장하면 안 된다. 실제로 선택한 $m$, 각 분기점에서 사용한 기호 규칙, 자식 방향별 기호 수, 위치 번호를 묶고 푸는 순서도 함께 저장해야 한다. 앨리스와 밥은 이 정보를 같은 방식으로 다시 계산한다.

앨리스가 실제 트리를 배치하는 과정

앨리스는 먼저 모든 입력 정점의 서브트리 크기를 계산한다.

현재 크기 제한이 $n$인 서브트리를 배치할 때, DP에서 선택한 $m$과 $C=n-m$을 사용한다. 크기가 $C$ 이상인 자식을 따라 중심 경로를 찾고, 각 위치의 $b_i$를 계산한다.

그 다음 $A_m$을 앞에서부터 보며 $b_i$ 이상인 값을 차례로 선택한다. 선택된 위치에는 실제 중심 경로 정점을 배치하고, 선택되지 않은 위치는 비워 둔다. 옆 자식들은 서브트리 크기 내림차순으로 정렬하여, 크기 상한이 충분한 자식 방향에 하나씩 배치한다.

실제 정점 $x$가 있는 분기점에서는 $x$의 번호를 $c$로 사용하여 각 자식 방향의 기호 $f_i(c)$를 정한다. 빈 위치에서는 실제로 사용되는 방향이 중심 경로의 연장 하나뿐이므로, 모든 유효한 라벨이 같은 방향으로 그대로 통과한다.

이 과정을 재귀적으로 반복하면 모든 입력 정점에 $U_{256}$ 안의 위치 번호가 하나씩 정해진다.

밥이 두 라벨에서 LCA를 찾는 과정

각 라벨에는 두 값이 들어 있다.

• 해당 정점의 $U_{256}$ 안 위치 번호
• 해당 정점의 원래 번호

밥은 두 위치 번호를 $U_{256}$의 맨 위에서부터 함께 읽는다.

• 한쪽 위치 번호가 현재 분기점의 $0$이면, 그 라벨의 정점이 현재 정점이다. 다른 정점은 그 아래에 있으므로 이 정점의 원래 번호를 반환한다.
• 두 기호가 같으면 두 정점은 같은 자식 방향에 있다. 두 위치 번호의 나머지 부분을 그 아래 설계도에서 계속 읽는다.
• 두 기호가 다르면 두 정점은 현재 입력 정점의 서로 다른 자식 서브트리에 있다. 두 기호로 현재 정점의 원래 번호를 복원하여 반환한다.

빈 설계도 위치에서는 모든 실제 정점이 중심 경로의 연장 방향 하나만 사용한다. 따라서 두 유효한 라벨이 빈 위치에서 서로 다른 방향으로 갈라지는 일은 없다. 밥이 처음 서로 다른 기호를 만나는 위치는 반드시 실제 입력 정점이 배치된 위치이다.

51비트 안에 넣기

위 DP와 기호 선택을 수행하면 $W_{51}(256)=10\,071\,518\,681\,788$을 얻는다.

위치 번호를 $s$, 원래 정점 번호를 $v$라 하고 $\operatorname{code}=256s+v$로 합친다. 필요한 코드 수는 $256W_{51}(256)=2\,578\,308\,782\,537\,728$이다.

이 문제에서는 라벨 길이 자체도 정보이며 앞의 $0$도 사라지지 않는다. 길이 $1$부터 $51$까지의 비어 있지 않은 모든 이진 문자열 수는 $2^1+2^2+\cdots+2^{51}=2^{52}-2$이다. 이 값은 필요한 코드 수보다 크다.

따라서 코드를 길이가 짧은 비트열부터 차례로 대응시키면 모든 라벨의 길이를 $51$ 이하로 만들 수 있다.

[서브태스크 2] $M=50$ (95점)

$M=51$의 중심 경로, 수열 $A_m$, $W(n)$ DP는 그대로 사용한다. 바뀌는 부분은 한 분기점에서 기호 공간을 세는 방법뿐이다.

$M=51$에서 남아 있는 낭비

$M=51$에서는 자식 방향 $i$마다 그 방향 전용 기호 블록을 만들었다. 방향 $i$가 기호를 $a_i$개 사용하고 아래 설계도의 위치 수가 $w_i$라면 이 방향은 $a_iw_i$개의 위치를 차지한다.

서로 다른 방향에서 같은 숫자의 기호를 사용하더라도 서로 다른 블록으로 취급했다. 이 중복을 없애면 위치 수를 더 줄일 수 있다.

큰 설계도는 작은 설계도를 대신할 수 있다

현재 분기점의 자식 방향에 붙는 설계도들을 받아 줄 수 있는 트리 크기가 큰 순서로 $G_0,G_1,\ldots$라 하자. 위치 수를 $w_0\geq w_1\geq\cdots$라 하자.

$G_0$는 가장 큰 트리를 받아 줄 수 있으므로, $G_1$에 들어갈 수 있는 트리도 받아 줄 수 있다. 일반적으로 $j<i$이면 $G_j$는 $G_i$가 받아 줄 수 있는 모든 트리를 받아 줄 수 있다.

따라서 논리적으로는 자식 방향 $i$에 속한 서브트리라도, 필요하다면 더 큰 $G_j$ 안에 다시 배치할 수 있다. 이 사실 덕분에 여러 자식 방향이 같은 기호 블록을 공유할 수 있다.

기호 하나에는 그 기호 다음에 어느 설계도로 들어갈지가 함께 정해져 있다고 생각하자. 정점 번호 $c$에서 자식 방향 $i$가 사용하는 기호를 $\tau_i(c)$라 한다. 다음 세 조건을 만족하면 된다.

• 기호가 여는 설계도는 자식 방향 $i$의 서브트리를 받아 줄 만큼 충분히 크다.
• 같은 정점 번호 $c$에서 서로 다른 자식 방향은 서로 다른 기호를 사용한다.
• 서로 다른 자식 방향에서 나온 기호 두 개를 알면 $c$를 유일하게 복원할 수 있다.

이제 위치 수는 자식 방향별 기호 수의 합이 아니라, 실제로 만들어 둔 서로 다른 기호 블록들의 크기 합으로 계산된다.

가장 큰 두 자식 방향의 기호를 공유하기

$G_0$를 여는 기호를 $x$개, $G_1$을 여는 기호를 $y$개 만든다.

각 기호를 점 하나로 생각하자. 다음 두 종류의 서로 다른 기호 쌍을 사용할 수 있다.

• $G_0$ 기호 두 개를 고르는 쌍: $\binom{x}{2}$개
• $G_0$ 기호 하나와 $G_1$ 기호 하나를 고르는 쌍: $xy$개

따라서 $\binom{x}{2}+xy\geq256$이면 $256$개의 정점 번호를 서로 다른 기호 쌍에 하나씩 대응시킬 수 있다.

정점 번호 $c$에 대응한 쌍의 두 기호를 첫 번째 자식 방향과 두 번째 자식 방향에 준다. 두 기호는 서로 다르므로 같은 정점 번호의 두 자식 방향이 같은 기호를 쓰지 않는다. 두 기호를 함께 보면 어느 쌍인지 알 수 있으므로 정점 번호 $c$도 복원할 수 있다.

두 기호가 모두 $G_0$를 여는 경우에는 두 번째 자식 서브트리도 $G_0$ 안에 다시 배치한다. $G_0$가 $G_1$보다 큰 트리를 받아 줄 수 있으므로 문제가 없다.

이 두 방향의 비용은 $xw_0+yw_1$이다. $M=51$에서처럼 두 방향에 독립된 직사각형 모양의 기호 공간을 주는 것보다 작아질 수 있다.

세 번째 이후 자식 방향의 기호

앞의 기호 쌍을 두 값 $a,b$로 나타내자. 서로 다른 기호에는 서로 다른 $0$이 아닌 값을 붙인다. 계산은 어떤 소수 $q$로 나눈 나머지 안에서 한다.

매개변수 $t$마다 새 값 $h_t=a+b+tab\pmod q$를 만든다. 세 번째 이후의 자식 방향에는 서로 다른 $t$를 하나씩 배정하고, 그 방향의 기호로 $h_t$를 사용한다.

이 값은 앞의 기호와 함께 사용했을 때 원래 쌍을 복원할 수 있도록 정해졌다.

값 $a$와 $h_t$를 알고 있고 $1+ta\neq0$이면, $b=(h_t-a)/(1+ta)$로 다른 끝값을 구할 수 있다.

서로 다른 $t,u$에 대한 $h_t,h_u$를 알고 있다면, 먼저 $ab=(h_t-h_u)/(t-u)$를 구하고, 이어서 $a+b=h_t-tab$를 구할 수 있다. 합과 곱을 알면 두 값 $a,b$의 쌍을 복원할 수 있다.

분모가 $0$이 되지 않도록, 사용 중인 모든 끝값 $z$에 대해 $1+tz\neq0$인 $t$만 사용한다. 이런 $t$를 안전한 값이라 하자. 끝값이 $x+y$개라면 안전한 $t$는 정확히 $q-(x+y)$개 존재한다.

안전한 $t$가 부족할 정도로 자식 방향이 많다면, 남은 방향에는 정점 번호 $c$를 그대로 저장하는 $256$개짜리 전용 기호 블록을 준다.

한 분기점의 비용

추가 자식 방향 중 $r$개를 $h_t$ 방식으로 처리한다고 하자. 한 분기점의 위치 수는 다음 값이다.

사용 가능한 선택은 $\binom{x}{2}+xy\geq256$, $x+y\leq q-1$, $r\leq q-(x+y)$를 만족해야 한다.

구현에서는 이 공유 방식과 $M=51$에서 사용한 독립 기호 방식들을 모두 비교하고, 실제 $w_i$에 대해 위치 수가 가장 작은 방법을 선택한다.

앨리스가 반드시 다시 배치해야 하는 경우

논리적 자식 방향 $i$가 원래 예정된 $G_i$가 아니라 더 큰 $G_j$를 여는 기호를 받을 수 있다.

이때 기존에 $G_i$에서 계산한 위치 번호의 첫 기호만 바꾸면 안 된다. 그 자식 서브트리를 처음부터 $G_j$ 안에 다시 배치해야 한다. 기호를 읽은 밥은 다음 설계도가 $G_j$라고 생각하기 때문이다.

$G_j$가 $G_i$보다 큰 트리를 받아 줄 수 있으므로 다시 배치는 항상 가능하다. 이 과정을 실제로 수행해야 앨리스와 밥의 해석이 일치한다.

50비트 안에 넣기

한 분기점의 비용을 위 방식으로 바꾸고, $M=51$과 같은 중심 경로 및 $A_m$ DP를 수행하면 $W_{50}(256)=8\,480\,600\,182\,708$을 얻는다.

위치 번호와 원래 정점 번호를 합친 코드 수는 $256W_{50}(256)=2\,171\,033\,646\,773\,248$이다.

길이 $1$부터 $50$까지의 비어 있지 않은 이진 문자열 수는 $2^{51}-2=2\,251\,799\,813\,685\,246$이다. 필요한 코드 수보다 크므로 모든 코드를 길이 $50$ 이하의 라벨에 대응시킬 수 있다.

구체적으로 길이 $\ell$인 비트열에는 코드 구간 $[2^\ell-2,2^{\ell+1}-3]$을 배정한다. 코드에서 구간의 시작값 $2^\ell-2$를 뺀 값을 정확히 $\ell$비트로 저장한다. 밥은 라벨의 실제 길이로 $\ell$을 알 수 있으므로 코드를 유일하게 복원한다.

밥이 위치 번호 두 개를 읽는 과정은 $M=51$과 같다. 한쪽이 현재 위치이면 그 정점 번호를 반환하고, 기호가 같으면 같은 다음 설계도로 내려가며, 기호가 다르면 기호 쌍으로 현재 LCA의 정점 번호를 복원한다.

Solution written by GPT5.6