진화

[서브태스크 1] $M=8$ (5점)

서브태스크 1에서는 모든 $1\leq i<N$에 대해 $P_i=i-1$이다. 조상 관계가 정점 번호의 대소 관계와 같으므로 $\operatorname{LCA}(u,v)=\min(u,v)$이다.

앨리스는 정점 번호를 $8$비트로 저장한다. 밥은 두 번호를 복원하여 작은 값을 반환한다.

[서브태스크 2] $M=2\,048$ (5점)

일반 트리에서 가장 직접적인 방법은 부모 배열을 라벨마다 전부 저장하는 것이다. 정점 번호 하나는 $8$비트이므로, 자신의 번호 $8$비트와 $P_1,P_2,\ldots,P_{255}$의 $2\,040$비트를 합치면 정확히 $2\,048$비트가 된다.

밥은 한 라벨에서 부모 배열 전체를 복원한다. 첫 번째 정점의 조상을 표시한 뒤 두 번째 정점에서 루트 방향으로 올라가며 처음 표시된 정점을 찾으면 된다.

이 풀이는 투 스텝 조건을 정확히 처리한다. 앨리스가 첫 실행에서 만든 전역 변수나 정적 변수는 두 번째 실행에 남지 않으므로, 밥에게 필요한 정보는 반드시 라벨 안에 있어야 한다.

[서브태스크 2] $M=128$ (60.14점)

각 정점에서 서브트리 크기가 가장 큰 자식 하나를 큰 자식으로 정하자. 큰 자식이 아닌 자식으로 내려가는 간선을 작은 간선이라 하자. 크기가 같은 자식이 여러 개라면 정점 번호가 작은 자식을 고르는 식으로 규칙을 고정한다.

작은 간선으로 이어진 자식 $c$를 생각하자. 같은 부모의 큰 자식은 크기가 $\operatorname{sz}(c)$ 이상이다. 따라서 부모를 $v$라 하면 $2\operatorname{sz}(c)\leq\operatorname{sz}(v)-1$이다. 작은 간선을 지날 때마다 현재 서브트리 크기가 절반보다 작게 줄어드므로, $N=256$에서는 한 루트-정점 경로에 작은 간선이 최대 $7$개이다.

DFS에서는 각 정점의 작은 자식들을 먼저 방문하고 큰 자식을 마지막에 방문한다. 정점 $x$의 진입 번호를 $\operatorname{tin}(x)$, 서브트리에서 가장 큰 DFS 번호를 $\operatorname{tout}(x)$라 하자.

루트에서 $x$까지 가며 지난 작은 간선을 $(p_0,c_0),(p_1,c_1),\ldots,(p_{k-1},c_{k-1})$라 하자. $p_i$는 부모이고 $c_i$는 작은 자식이다. $x$의 라벨에는 $\operatorname{tin}(x)$, 모든 $p_i$, 모든 $\operatorname{tout}(c_i)$, 그리고 $x$의 원래 번호를 저장한다.

두 라벨 중 $\operatorname{tin}$이 작은 정점을 $x$, 큰 정점을 $y$라 하자. $x$의 작은 간선 기록을 루트 쪽부터 확인한다. 처음으로 $\operatorname{tin}(y)>\operatorname{tout}(c_i)$가 되면 답은 $p_i$이다. 그런 기록이 없으면 답은 $x$이다.

정확성을 증명하자. $x$가 $y$의 조상이면, 루트에서 $x$까지 지나온 모든 작은 자식 쪽 서브트리가 $y$도 포함하므로 실패하는 기록이 없다.

두 정점이 조상 관계가 아니고 $l=\operatorname{LCA}(x,y)$라 하자. $l$에서 $x$ 방향이 큰 자식 방향이고 $y$ 방향이 작은 자식 방향이라면, 작은 자식을 먼저 방문하는 DFS 때문에 $y$의 번호가 더 작아야 한다. 이는 $\operatorname{tin}(x)<\operatorname{tin}(y)$와 모순이다. 따라서 $l$에서 $x$ 방향의 첫 간선은 작은 간선이다. 그 전의 작은 자식 쪽 서브트리들은 두 정점을 모두 포함하지만, 이 작은 자식 쪽 서브트리부터는 $x$만 포함한다. 그러므로 처음 실패하는 기록의 부모가 정확히 $l$이다.

작은 간선 기록은 최대 $7$개이다. $\operatorname{tin}$과 자신의 번호가 각각 $8$비트이고, 기록마다 부모와 경계가 각각 $8$비트이므로 총 길이는 $8+7\cdot16+8=128$비트이다.

[서브태스크 2] $M=99$ (68.17점)

밥은 $\operatorname{tout}(c_i)$의 정확한 값이 아니라, 이를 $\operatorname{tin}(y)$와 비교할 수 있기만 하면 된다. 따라서 각 작은 간선에 대해 $d_i=\operatorname{tout}(c_i)-\operatorname{tin}(x)$를 저장한다. 그러면 밥은 $\operatorname{tin}(y)-\operatorname{tin}(x)>d_i$인지 확인하여 기존과 같은 판정을 할 수 있다.

$i$번째 작은 간선 뒤의 서브트리 크기는 최대 $2^{7-i}-1$이다. 또한 $x$도 그 서브트리 안에 있으므로 $0\le d_i\le \operatorname{sz}(c_i)-1\le 2^{7-i}-2$이다. 따라서 각 $d_i$를 저장하는 데 필요한 비트 수는 차례로 $7,6,5,4,3,2,0$비트이며, 합은 $27$비트이다.

결국 $\operatorname{tin}(x)$에 $8$비트, 작은 간선의 부모 번호에 최대 $7\cdot8=56$비트, 상대 경계에 $27$비트, 자신의 정점 번호에 $8$비트를 사용하므로 $8+56+27+8=99$비트로 라벨을 구성할 수 있다.

[서브태스크 2] $M=91$ (71.02점)

작은 간선의 개수를 $k$라 하고, 상대 경계값들을 모은 수열 $(d_0,d_1,\ldots,d_{k-1})$을 경계 수열이라 하자.

작은 간선이 $7$개라면 서브트리 크기는 매 단계 가능한 최댓값으로 줄어들어야 한다. 따라서 각 단계의 서브트리 크기와 경계 수열이 유일하게 정해지므로, 경계값을 라벨에 따로 저장할 필요가 없다.

작은 간선이 $6$개 이하인 경우에는 $M=99$와 같이 경계 수열을 저장한다. 최악은 $k=6$일 때이며, $\operatorname{tin}(x)$에 $8$비트, 부모 번호에 $48$비트, 경계 수열에 $27$비트, 자신의 정점 번호에 $8$비트를 사용하므로 총 $91$비트이다. $k=7$인 경우에는 부모 번호가 $56$비트로 늘어나지만 경계 수열을 저장하지 않으므로 더 짧다.

[서브태스크 2] $M=84$ (73.84점)

각 경계를 독립적으로 저장하지 말고, 가능한 경계 수열 전체에서 몇 번째인지 저장하자.

작은 간선이 $k$개이고, $i$번째 기록 뒤에 남은 작은 간선 수를 $t=k-i-1$이라 하자. 뒤에 남은 큰 자식 쪽 서브트리들이 차지해야 하는 최소 크기 때문에 $d_i$에는 강제 하한 $B_i=2^{t+1}-t-2$가 있다. $z_i=d_i-B_i$라 두면 각 $z_i$는 음이 아니고, 연속한 기록 사이의 크기 관계에서 $z_i\geq z_{i+1}$을 얻는다. 또한 각 위치에는 상한 $A_i=2^{7-i}-2^{k-i}$가 있다.

따라서 가능한 경계 정보는 $A_0\geq z_0\geq z_1\geq\cdots\geq z_{k-1}\geq0$을 만족하는 짧은 단조 수열이다.

$F(pos,prev)$를 $pos$번째 이후를 채우는 방법 수라 하자. 현재 값은 $0$부터 $\min(prev,A_{pos})$까지 고를 수 있으므로 작은 DP로 모든 수열의 개수를 세고, 가능한 수열을 작은 값부터 정렬했을 때의 순번을 계산하고, 순번만으로 수열을 다시 복원할 수 있다.

앨리스는 $z$ 수열의 순번을 저장한다. 밥은 $k$와 순번을 읽어 수열을 복원하고, $d_i=z_i+B_i$로 원래 경계를 되찾는다. 이후 LCA 판정은 $M=128$과 같다.

[서브태스크 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$이다.

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

합이 $m$ 이하인 임의의 양의 정수열 $b_1,b_2,\ldots,b_t$를, 미리 정한 하나의 수열 안에 순서를 유지하며 넣고 싶다.

모든 작은 합을 받아 주는 수열 $A_m$

수열 $A_m$을 다음과 같이 만든다.

$$\begin{align*} A_0&=(),\\ A_m&=A_{\lfloor(m-1)/2\rfloor}+[m]+A_{\lceil(m-1)/2\rceil}. \end{align*}$$

예를 들어 $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$ 방식으로 처리한다고 하자. 한 분기점의 위치 수는 다음 값이다.

$$\begin{align*} 1+xw_0+yw_1 +q\sum_{i=2}^{r+1}w_i +256\sum_{i=r+2}^{d-1}w_i. \end{align*}$$

사용 가능한 선택은 $\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