Evolution

This is a tree-labeling problem. Alice knows the complete tree, while Bob must recover an LCA from two short labels without knowing the tree. Distinguishing the two queried vertices is not enough: when their encoded paths diverge, Bob must also recover the original vertex number of the branching point.

We first develop a direct structural encoding and see where it stops. We then place every possible input tree inside a fixed recursive universal grammar. The final improvement shares tag namespaces between child grammars and reduces the maximum label length to $50$ bits.

Subtask 1: the tree is a path

If $P_i=i-1$ for every $1\leq i<N$, ancestry is exactly the order of vertex numbers. Hence

$$\operatorname{LCA}(u,v)=\min(u,v).$$

Alice stores each vertex number in $8$ bits. Bob decodes the two numbers and returns the smaller one, so this subtask has $M=8$.

For a general tree, the two vertex numbers do not determine their LCA. The labels must also describe enough of the tree structure.

Baseline: store the complete tree

Since $N=256$, a vertex number takes $8$ bits. Every label can contain

• its own vertex number in $8$ bits;
• $P_1,P_2,\ldots,P_{255}$ in bits.

The total is exactly $2\,048$ bits. Bob reconstructs the full parent array from either label and computes the LCA directly.

This baseline is important because it obeys the communication model without relying on shared global state.

First compression: heavy-light decomposition

At each vertex, choose a child of maximum subtree size as the heavy child. Every other child edge is light. Ties are broken deterministically.

If $c$ is a light child of $v$ and $h$ is the heavy child, then

$$\operatorname{sz}(h)\geq\operatorname{sz}(c),$$

and therefore

$$2\operatorname{sz}(c)\leq\operatorname{sz}(v)-1.$$

Every light edge reduces the current subtree size by more than a factor of two. For $N=256$, a root-to-vertex path contains at most seven light edges.

Run a DFS that visits every light child first and the heavy child last. Let $\operatorname{tin}(x)$ be the entry time of $x$ and $\operatorname{tout}(x)$ the final entry time in its subtree.

Suppose the light edges on the path to $x$ are

$$(p_0,c_0),(p_1,c_1),\ldots,(p_{k-1},c_{k-1}),$$

where $p_i$ is the parent and $c_i$ is the light child. Store

• $\operatorname{tin}(x)$;
• every $p_i$;
• every $\operatorname{tout}(c_i)$;

Of two labels, call the vertex with smaller entry time $x$ and the other one $y$. Scan the light records of $x$ from the root side. At the first record satisfying

$$\operatorname{tin}(y)>\operatorname{tout}(c_i),$$

return $p_i$. If no record fails, return $x$.

Let $l=\operatorname{LCA}(x,y)$ and assume neither vertex is an ancestor of the other. Because light children are visited before the heavy child and $\operatorname{tin}(x)<\operatorname{tin}(y)$, the first edge from $l$ toward must be light. Earlier recorded light subtrees contain both vertices, while this one contains but not . Thus the first failed record has parent exactly .

There are at most seven records, so this scheme uses

$$8+7\cdot16+8=128$$

bits.

Compressing the HLD labels

The same decoder can be retained while the boundaries are represented more compactly.

For a vertex $x$, store the relative tail

$$d_i=\operatorname{tout}(c_i)-\operatorname{tin}(x)$$

instead of the absolute $\operatorname{tout}(c_i)$. The size bound after the $i$-th light edge gives

$$0\leq d_i\leq2^{7-i}-2.$$

The maximum total number of bits for all tails is

$$7+6+5+4+3+2=27,$$

which yields a $99$-bit scheme.

There is additional dependence between the tails. If there are $k$ light edges and $t=k-i-1$ light edges remain after record $i$, define

$$B_i=2^{t+1}-t-2$$

and

$$z_i=d_i-B_i.$$

The forced heavy subtrees imply

$$A_0\geq z_0\geq z_1\geq\cdots\geq z_{k-1}\geq0$$

for small known bounds $A_i$.

A tiny DP counts these monotone sequences and supports ranking and unranking them. For $k=6$, there are $939\,993$ possible sequences. Instead of reserving a fixed $20$-bit field, use all bit strings of lengths $15$ through $19$:

$$2^{15}+2^{16}+2^{17}+2^{18}+2^{19}=1\,015\,808.$$

The actual vector length identifies the block. This gives an $83$-bit construction.

This HLD family is a useful direct description of the input tree. Its bottleneck is also clear: up to seven original light-ancestor numbers already cost $56$ bits. To reach $50$, we must stop listing ancestor numbers and DFS boundaries explicitly.

A new viewpoint: a universal grammar

Let $U_n$ be a fixed recursive structure capable of representing every rooted tree of size at most $n$ while preserving LCAs. Both programs construct the same $U_{256}$ independently; it does not depend on the input tree.

Alice embeds every input vertex $v$ into a state $\operatorname{state}(v)$ of $U_{256}$. Its label stores this state together with the original vertex number $v$.

Consider one local node of the grammar. State $0$ represents the current location. Every nonzero state consists of a tag selecting a child grammar and a substate inside that grammar.

Let the original input vertex represented at this local node have color

$$c\in\{0,1,\ldots,255\}.$$

For every logical child direction $i$, assign a tag $f_i(c)$. The tag system must satisfy three properties.

1. For one color, different logical children receive different tags.
2. Tags from any two different logical children uniquely determine the color.
3. The grammar opened by a tag is large enough for the corresponding child subtree.

Bob parses the two states simultaneously. If the tags first become different at a local node, the two input vertices lie in different child directions of the current input vertex. That input vertex is their LCA, and the two tags reveal its color, which is its original number.

If the tags are equal, both states continue in the same logical direction. If either state is $0$, that label's vertex is the current location and is therefore the LCA.

It remains to build a small grammar that can embed every tree.

A universal sequence for bounded total mass

Define

$$A_0=()$$

and

$$A_m=A_{\lfloor(m-1)/2\rfloor}+[m]+A_{\lceil(m-1)/2\rceil}.$$

The key lemma is the following.

For every positive integer sequence

$$b_1,b_2,\ldots,b_t$$

with total sum at most $m$, one can choose an order-preserving subsequence

$$a_1,a_2,\ldots,a_t$$

of $A_m$ such that $b_i\leq a_i$ for every .

To prove it, find the first term at which the prefix sum exceeds $\lfloor(m-1)/2\rfloor$ and match it to the central value $m$. The sum before it fits in the left recursive sequence, and the sum after it fits in the right recursive sequence. Apply induction to both sides.

Embedding an arbitrary tree

When constructing $U_n$, choose

$$0\leq m\leq\left\lfloor\frac{n-1}{2}\right\rfloor$$

and set

$$C=n-m.$$

Then $C>n/2$.

In any input subtree, there is at most one child of size at least $C$. Repeatedly following such a child produces a spine.

Except for the final spine subtree, let $b_i$ be one plus the total size of the side subtrees attached at the $i$-th spine vertex. At most $m$ vertices lie outside the final large subtree, so

$$\sum b_i\leq m.$$

Use the universal sequence lemma to assign these values to an order-preserving subsequence of $A_m$.

At a wrapper with assigned capacity $a_i$, sort the side child sizes as

$$s_1\geq s_2\geq\cdots.$$

Their sum is at most $a_i-1$, hence

$$s_r\leq\left\lfloor\frac{a_i-1}{r}\right\rfloor.$$

The wrapper therefore has a continuation child for the spine and side child grammars with capacities

$$a_i-1,\left\lfloor\frac{a_i-1}{2}\right\rfloor, \left\lfloor\frac{a_i-1}{3}\right\rfloor,\ldots.$$

At the final spine vertex, the first child grammar has capacity $C-1$, and the remaining ranked child grammars have capacities

$$\left\lfloor\frac{n-1}{2}\right\rfloor, \left\lfloor\frac{n-1}{3}\right\rfloor,\ldots.$$

By recursion, all side subtrees and the final subtree can be embedded. Thus this construction represents every rooted tree of size at most $n$.

Dynamic programming for the number of states

Let $W(n)$ be the number of states in $U_n$.

$$W(0)=0,\qquad W(1)=1.$$

For every $n$, try every valid $m$. Build the final local node and then the wrappers of $A_m$ backwards. Replace every child capacity $s$ by the previously computed state count $W(s)$, evaluate the required local state count, and keep the smallest construction.

The DP also stores the chosen decomposition and local tag scheme. The implementation reconstructs the actual grammar, the state wrapping operation, and its inverse parser; merely computing the numerical cost would not be sufficient.

A $51$-bit local code

For two logical children with grammar sizes $w_0,w_1$, choose $L,R$ with $LR\geq256$ and encode color as

$$(c\bmod L,\lfloor c/L\rfloor).$$

The local cost is

$$1+Lw_0+Rw_1.$$

With more children, one may use several pairwise-decodable codes.

• Different children omit disjoint subsets of the eight color bits, so any two tags together contain all bits.
• View the color as two coordinates $(x,y)$ over a finite field, and give children coordinates such as $x$ and $y+tx$. Any two distinct coordinates recover $(x,y)$.

Choosing the cheapest valid local code for every weight vector gives a $51$-bit universal construction. One further saving is needed for full score.

The $50$-bit idea: shared tag namespaces

Let the child grammar state counts be

$$w_0\geq w_1\geq w_2\geq\cdots.$$

Instead of giving the first two expensive children independent tag namespaces, let them share part of the tag space.

Create $x$ level-$0$ tags, each opening the largest grammar $G_0$, and $y$ level-$1$ tags, each opening $$. Use the following undirected edges:

• an edge between two distinct level-$0$ tags;
• an edge between a level-$0$ tag and a level-$1$ tag.

There are

$$\binom{x}{2}+xy$$

such edges. If this number is at least $256$, map the $256$ colors injectively to edges and give the two endpoints to the first two logical children.

For a level-$0$--level-$0$ edge, both children open $G_0$. Since $G_0$ is at least as capable as , the second child subtree can be re-embedded into . For a level---level- edge, each child opens its nominal grammar.

The endpoints of an edge are distinct, and the edge uniquely identifies the color. The cost of the first two children becomes

$$xw_0+yw_1.$$

Finite-field coordinates for later children

Map all endpoint tags to distinct nonzero elements $a,b$ of a prime field $\mathbb{F}_q$, requiring $x+y\leq q-1$. For a parameter , define

$$h_t=a+b+tab\pmod q.$$

Call $t$ safe if

$$1+tz\neq0\pmod q$$

for every endpoint $z$ in use. Parameter $0$ is always safe. For nonzero $t$, exactly one field element $z=-1/t$ is forbidden, so there are exactly

$$q-(x+y)$$

safe parameters.

Assign a distinct safe parameter to each additional field-coded child and use a separate namespace of $q$ tags for its value $h_t$.

From an endpoint $a$ and $h_t$,

$$b=\frac{h_t-a}{1+ta}.$$

The denominator is nonzero by safety.

From two field values $h_t,h_u$ with $t\neq u$,

$$ab=\frac{h_t-h_u}{t-u},$$

and

$$a+b=h_t-t(ab).$$

Thus $a,b$ are the two roots of

$$X^2-(a+b)X+ab,$$

which identifies the graph edge and hence the color.

If more children remain, give each one a private $256$-tag namespace storing the color directly.

With $r$ field-coded children, the local cost is

$$1+xw_0+yw_1 +q\sum_{i=2}^{r+1}w_i +256\sum_{i=r+2}^{d-1}w_i,$$

subject to

$$\binom{x}{2}+xy\geq256, \qquad x+y\leq q-1, \qquad r\leq q-(x+y).$$

The reference construction compares every useful shared pattern with the independent local-code candidates and keeps the cheapest valid scheme.

Tags that open a larger grammar

A subtle but essential point is that a logical child may use a shared tag opening an earlier, larger grammar rather than its nominal grammar. Alice must not construct a state in the nominal grammar and merely replace the tag. She must re-embed that child subtree into the grammar actually referenced by the tag.

The child grammars are nested by capacity, so the larger grammar always accepts the smaller subtree. This re-embedding is what makes shared tags valid.

Final state count and variable-length encoding

Putting the shared local code into the universal DP gives

$$W_{50}(256)=8\,480\,600\,182\,708.$$

The selected top-level decomposition has $m=87$ and $C=169$.

Combine the universal state and the original vertex number as

$$\operatorname{code}=256\cdot\operatorname{state}+\operatorname{own}.$$

The number of required codes is

$$256W_{50}(256)=2\,171\,033\,646\,773\,248.$$

The number of nonempty binary strings of lengths from $1$ through $50$ is

$$2^1+2^2+\cdots+2^{50} =2^{51}-2 =2\,251\,799\,813\,685\,246,$$

which is larger.

For length $\ell$, define

$$\operatorname{start}(\ell)=2^\ell-2.$$

If a code lies in

$$[2^\ell-2,2^{\ell+1}-3],$$

store

$$\operatorname{code}-\operatorname{start}(\ell)$$

as exactly $\ell$ bits. Bob knows $\ell$ from the vector length and reconstructs the code uniquely.

Therefore every label has length at most $50$.

Bob's decoder

Decode both labels into

$$\operatorname{own}=\operatorname{code}\bmod256, \qquad \operatorname{state}=\left\lfloor\frac{\operatorname{code}}{256}\right\rfloor.$$

Parse the two states simultaneously from the root grammar.

• If one state is $0$, that label's vertex is represented at the current location. It is an ancestor of the other vertex and is the LCA.
• If the two tags are equal, both paths use the same logical child. Continue with the two substates in the common next grammar.
• If the tags differ, the input paths diverge at the current input vertex. Decode its original number from the tag pair and return it.

For a fixed color, tags of different logical children are distinct, and any valid pair from different children uniquely determines the color. Hence every case is correct.

An unused universal wrapper does not contain an actual input vertex with occupied side children, so two valid input paths cannot first diverge there. The first differing tags always correspond to the true LCA in the input tree.

Two-stage implementation details

Alice and Bob independently build the same deterministic universal DP and local schemes. No runtime pointer, table, global variable, or file created by Alice is needed by Bob. Identical constants, tie-breaking, and state enumeration are sufficient for both processes to interpret the labels consistently.

Do not assume $P_i<i$. Build the children lists from $P$ and traverse the tree from root $0$.

This construction proves $M\leq50$ and therefore earns all $100$ points. It does not claim a lower bound excluding $49$-bit labelings.

Solution written by GPT5.6