Al Fine (Maximizing Version)

Normalize The Permutations

Let $pos_b[x]$ be the position of vertex $x$ in Arietta's order $b$. Replace Tortinita's order by

$c_i = pos_b(a_i)$.

Now Arietta's order is just $1,2,...,n$, and Tortinita's order is the permutation $c$. The root $0$ is outside this array and will be handled by adding one final edge at the end.

What A Common Subtree Looks Like

In a DFS preorder, every subtree appears as one contiguous segment, with the subtree root first.

So a segment $c[l..r]$ can be one common subtree iff:

• its first element is the root in both orders, so $c[l]$ must be the minimum value in the segment;
• its values must be consecutive in Arietta's identity order.

Because $c$ is a permutation, this becomes the clean condition:

$min(c[l..r]) = c[l]$ and $max(c[l..r]) - min(c[l..r]) = r-l$.

Call such a segment valid.

This is the core translation. Everything else is just engineering around the fact that there can be way too many valid segments. In the identity permutation, every segment is valid, so brute force is hilariously dead.

Depth Means Nesting

A root-to-leaf path in the tree gives nested subtrees. Therefore, after normalization, we want the longest chain of nested valid segments.

Conversely, if we have nested valid segments, we can realize them in an actual tree: make the next segment on the chain one child subtree, and attach everything else as singleton child subtrees. Since DFS child order is arbitrary in each sequence, this works.

Important: this is why LIS is bait. Same relative order only says ancestors appear before descendants. It does not force the descendants to stay inside one contiguous DFS subtree block. DFS is pickier than that.

Why Only The Largest Segment Per Start Matters

For each $l$, let $R[l]$ be the largest $r>l$ such that $c[l..r]$ is valid. If no non-singleton valid segment starts at $l$, set $R[l]=0$.

The useful fact is: maximal segments do not cross.

Suppose $[l,R[l]]$ and $[x,R[x]]$ cross, with $l < x \le R[l] < R[x]$. Since $x$ lies inside the first valid segment, $c[x]$ lies inside its consecutive value interval. The second segment also has a consecutive value interval starting at $c[x]$, so the two value intervals overlap. Their position intervals overlap too, so their union $[l,R[x]]$ also has consecutive values and still has minimum $c[l]$. That means $[l,R[x]]$ is valid, contradicting the maximality of $R[l]$.

So the maximal valid segments form a laminar family: they are nested or disjoint. This lets us sweep them like DFS intervals.

When scanning $i=1..n$, keep a stack of active right endpoints. Before processing $i$, pop every endpoint $\le i$. If $R[i] \ne 0$, push it. The largest stack size is the largest number of nested non-singleton valid segments.

Why output stack_max + 1? The stack counts non-root non-singleton blocks. The real tree also has the edge from root $0$ into the first block, or directly into a vertex if there are no blocks. The innermost non-singleton block can always go one more edge to a singleton leaf. So the final answer is exactly max_stack_size + 1.

Computing All $R[l]$

We need the largest valid segment starting at every $l$ in $O(n \log n)$.

Use divide and conquer over index ranges. For a recursive range $[L,R]$ with midpoint $mid$, recursively solve the left and right halves. Now only handle valid segments $[i,j]$ that cross the midpoint: $i \le mid < j$.

Precompute:

• for the left half, suffix minima/maxima of $c[i..mid]$;
• for the right half, prefix minima/maxima of $c[mid+1..j]$.

For a crossing valid segment, $c[i]$ must be the minimum on the left suffix. If it is not, skip $i$.

Let:

• $mn_i = min(c[i..mid])$,
• $mx_i = max(c[i..mid])$,
• $mn_j = min(c[mid+1..j])$,
• $mx_j = max(c[mid+1..j])$.

We need $mn_j > mn_i$, because the global minimum must be $c[i]=mn_i$.

Now split by where the maximum lies.

Case 1: maximum is on the left.

Then the global maximum is $mx_i$, so:

$mx_i - mn_i = j-i$.

Thus $j = i + mx_i - mn_i$ is forced. We just check that $j$ is in the right half, $mn_j > mn_i$, and $mx_j < mx_i$.

Case 2: maximum is on the right.

Then:

$mx_j - mn_i = j-i$,

so:

$mx_j - j = mn_i - i$.

For every right prefix endpoint $j$, bucket it by the key $mx_j-j$. For a fixed $i$, we only need the bucket with key $mn_i-i$. Inside that bucket, endpoints are processed in increasing order; prefix minima only decrease, and prefix maxima only increase. A moving pointer finds the largest endpoint whose right minimum is still greater than $mn_i$, then we check that its right maximum beats the left maximum.

Each divide-and-conquer level does linear work over its range, so the total time is $O(n \log n)$.

Then the stack sweep gives the answer in $O(n)$.