Rae Taylor and Trees (hard version)

Core Idea

Make the implicit graph where vertices are $1,2,\dots,n$, and an edge $(u,v)$ with $u<v$ exists iff $u$ appears before $v$ in the permutation.

The problem asks for a tree using only valid edges. That exists iff this graph is connected. If it is connected, any spanning tree works. If it is disconnected, no tree can magically teleport across components. Sad, but math is rude like that.

So we just need to construct a spanning forest of this graph efficiently, and check whether it has one component.

Process The Permutation Left To Right

Suppose we are currently reading value $x$.

All previously read values appeared before $x$ in the permutation. For an already-seen value $y$:

• if $y < x$, then $(y,x)$ is a valid edge;
• if $y > x$, then $(x,y)$ would require $x$ to appear before $y$, which is false, so no edge.

So when $x$ arrives, it connects exactly to the already-processed values smaller than $x$.

That is the entire trick. No DP circus needed.

Representing Components

Look at the connected components formed by the values we have processed so far.

For a component $C$, when does the new value $x$ connect to it?

It connects iff $C$ contains some value smaller than $x$.

That is equivalent to:

$$\min(C) < x$$

So each current component only needs one piece of information: its minimum label.

If a component has minimum $m < x$, then we can safely add the edge $(m,x)$:

• $m < x$ by definition;
• $m$ appeared earlier because it is already processed;
• therefore the edge is valid.

This merges $x$ with that whole component. If several components have minima smaller than $x$, $x$ merges all of them, and we output one edge per merged component.

If a component has minimum greater than $x$, then all labels in that component are greater than $x$, so $x$ has no edge to it right now.

Algorithm

Maintain a sorted set comps, containing the minimum label of every current component.

For every value $x$ in permutation order:

1. Let the new merged component initially have minimum $x$.
2. While the smallest element of comps is less than $x$:
   • remove it; call it $m$;
   • add edge $(m,x)$;
   • merge that component into $x$'s component;
   • update the new minimum.
3. Insert the new component minimum back into comps.

At the end:

• if comps.size() == 1, the graph is connected, so print Yes and all chosen edges;
• otherwise print No.

Why The Edges Form A Tree When Connected

Every printed edge connects two different current components. So we never create a cycle.

Each printed edge reduces the number of components by $1$. After all $n$ vertices are processed, if exactly one component remains, then we printed exactly $n-1$ edges. A connected acyclic graph with $n-1$ edges is a tree. Boom.

Complexity

Each printed edge corresponds to one removed component minimum. There are at most $n-1$ such removals. Each set operation costs $O(\log n)$.

Total complexity per test case is:

$$O(n \log n)$$

Memory usage is $O(n)$.