Anya Loves Trees!

The crucial observation is that the target order is completely fixed. The positive leaf values form a permutation of $1,2,...,k$, so a strictly increasing arrangement can only be

$1,2,...,k.$

Subtrees can never be interleaved

For any vertex $u$, all leaves in the subtree of $u$ always appear consecutively in the left-to-right leaf traversal. Rotating children can move entire child subtrees around, but it cannot split one subtree and insert unrelated leaves into its middle.

Consequently, in the final sequence $1,2,...,k$, the leaves belonging to any subtree must occupy consecutive positions. Their values must therefore form an integer interval.

This is stronger than merely asking whether that subtree's values can be sorted. For example, a subtree containing values $1$ and $3$ could locally produce $[1,3]$, but it can never fit into the global sequence while value $2$ belongs to another subtree: that other leaf cannot be inserted between them.

The bottom-up invariant

For each vertex $u$, we determine whether its subtree can become one valid consecutive block

$L_u,L_u+1,...,R_u.$

If it can, we store the endpoints $[L_u,R_u]$.

For a leaf containing $a_u$, this is immediate:

$L_u=R_u=a_u.$

Now consider an internal vertex whose children, in their original order, are

$c_0,c_1,...,c_{d-1}.$

Assume their subtrees have already been checked and return valid intervals. Each child can internally produce its values in increasing order. What remains is arranging those child intervals.

What rotations actually allow

Repeated left shifts do not allow an arbitrary permutation of the children. They allow only cyclic rotations:

$c_s,c_{s+1},...,c_{d-1},c_0,...,c_{s-1}.$

So just sorting the child intervals would be cheating—the operation never gave us that superpower.

In a valid increasing concatenation, the first interval must be the one with the smallest left endpoint. Let its position in the original child list be $s$. That forces the only potentially successful rotation: start at $c_s$ and then follow the children cyclically.

For the resulting blocks to join without a gap or inversion, every boundary must satisfy

$R_{current}+1=L_{next}.$

If every boundary passes, their concatenation is exactly one consecutive interval. We set

• $L_u$ to the smallest left endpoint;
• $R_u$ to the right endpoint of the final child in that cyclic walk.

There is deliberately no check from the last child back to the first. The output after choosing a rotation is a linear sequence, not some cursed circular permutation where $k$ must connect back to $1$.

Intervals belonging to different children cannot overlap because all leaf values are distinct. Therefore the child with minimum $L$ is unique, and we can find it with a linear scan. No sorting is necessary.

Correctness proof

We prove by induction over subtrees that the algorithm accepts a vertex $u$ exactly when its leaves can occupy one consecutive increasing block, and that the stored endpoints describe that block.

Base case. If $u$ is a leaf with value $a_u$, its leaf sequence is already the one-element interval $[a_u,a_u]$. The algorithm returns exactly that.

Necessity. Suppose an internal subtree rooted at $u$ can form a consecutive increasing block. Every child subtree occupies a contiguous part of that block, so each child must itself form a consecutive increasing interval. By the induction hypothesis, all children pass our checks.

The child blocks must appear in increasing interval order. Their first block is therefore the one with minimum left endpoint. Since the order of children can only be cyclically rotated, walking cyclically from that child must reproduce the increasing block order. Adjacent blocks in a consecutive interval have no missing value, so every checked equality $R_{current}+1=L_{next}$ must hold. Thus the algorithm accepts $u$.

Sufficiency. Suppose every child passes and all boundary equalities pass when walking cyclically from the minimum-left child. By the induction hypothesis, arrange every child internally into its stored increasing interval. Rotate the children of $u$ so the minimum-left child comes first. The boundary equalities make these intervals concatenate into

$L_u,L_u+1,...,R_u.$

Hence the subtree of $u$ forms a valid consecutive increasing block.

By induction, the invariant holds for every vertex. At the root, all leaves are included, so the required final sequence exists exactly when its interval is $[1,k]$. Therefore the algorithm prints the correct answer.

Implementation details

The parent of a vertex may have a larger index, so processing vertices in decreasing numerical order is not valid. We first traverse from root $1$ to create an order in which every parent appears before its children, then process that order in reverse.

This also avoids recursive DFS: a chain of length $2\cdot10^5$ is a pretty dumb reason to gamble on the call stack.

Every edge is scanned a constant number of times, giving:

• Time: $O(n)$ per test case;
• Extra space: $O(n)$.

The total $n$ over all test cases is at most $2\cdot10^5$.