진화

[서브태스크 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] $M=128$ (60.14점)

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

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

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})$라 하자. 는 부모이고 는 작은 자식이다. 의 라벨에는 , 모든 , 모든 , 그리고 의 원래 번호를 저장한다.

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

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

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

작은 간선 기록은 최대 $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)$를 저장한다. 그러면 밥은 인지 확인하여 기존과 같은 판정을 할 수 있다.

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

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

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

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

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

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

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

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

작은 간선이 $k$개이고, $i$번째 기록 뒤에 남은 작은 간선 수를 $t=k-i-1$이라 하자. 뒤에 남은 큰 자식 쪽 서브트리들이 차지해야 하는 최소 크기 때문에 $d_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$ 이하인 임의의 양의 정수열 $b_1,b_2,\ldots,b_t$를, 미리 정한 하나의 수열 안에 순서를 유지하며 넣고 싶다.

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

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

$$\begin{array}{rl}{\displaystyle A_0}& {\displaystyle =(),}\\ {\displaystyle A_{}}\end{array}$$