To the Infinity

The core trick is to stop looking at the expression tree as exponentiation syntax and start looking at what is inside the exponent of base $x$.

Every function in this problem can be written as a power tower object:

$$f(x)=x^{X_1X_2\cdots X_m},$$

where each $X_i$ is another function of the same kind. For a leaf, $f(x)=x$, so the product is empty.

That empty product is important: a leaf is the smallest possible object.

How The Representation Updates

Suppose node $u$ has children $l$ and $r$.

If

$$f_l(x)=x^{X_1X_2\cdots X_m},$$

then

$$f_u(x)=f_l(x)^{f_r(x)} =\left(x^{X_1X_2\cdots X_m}\right)^{f_r(x)} =x^{X_1X_2\cdots X_m\cdot f_r(x)}.$$

So node $u$ inherits all exponent factors from its left child, then adds one new factor: the whole function $f_r$.

Define $M_u$ as the multiset of factors in the exponent of $f_u$.

Then:

• if $u$ is a leaf, $M_u=\varnothing$;
• otherwise,

$$M_u=M_{l_u}\cup\{f_{r_u}\}.$$

That is the actual structure of the problem. The left child contributes an old multiset. The right child contributes one new factor.

Comparing Two Nodes

Since every node is $x^{\text{something}}$ and $x>1$, comparing functions is the same as comparing their exponent products.

So compare two multisets of factors:

$$M_A=\{A_1,A_2,\ldots\},\qquad M_B=\{B_1,B_2,\ldots\}.$$

Sort both in decreasing order of growth. Then compare them lexicographically.

Equivalently, if every distinct function has a rank, look at the largest rank where the two multisets have different counts. The multiset with the larger count at that rank is larger.

Why does this work?

Because if one factor $P$ grows faster than every remaining factor on the other side, then $P$ beats any constant-size product of those smaller factors. There is no hidden “but maybe three smaller towers catch up” nonsense here. A bigger tower crushes finitely many smaller towers.

So the factor multiset fully determines the function.

Equal multisets mean equal functions. Different multisets mean one eventually wins.

Why We Can Rank Nodes Online

We need ranks of factors to build these multisets. But a node uses its right child as a factor, so we need the right child’s rank first.

Luckily, every child is smaller than its parent.

For the left child:

$$f_l < f_l^{f_r}=f_u$$

for large $x$.

For the right child, $f_u$ is also larger, because $f_l\ge x$, so $f_l^{f_r}$ grows way past $f_r$.

Therefore, before a node can appear in the global sorted order, both of its children must already appear.

So we can do a Kahn-style process:

1. All leaves are ready.
2. Put ready nodes into a priority queue ordered by their function value.
3. Pop the smallest node, output it, and assign its rank.
4. When both children of a parent have been popped, we can build the parent’s multiset and push it.

The smallest unprocessed node is always ready. If it were not ready, it would have an unprocessed child smaller than itself, contradiction. Neat and brutal.

Persistent Segment Tree

A multiset is stored as counts over ranks.

For node $u$:

• root[u] stores the multiset $M_u$;
• leaves have an empty tree;
• for an internal node,

$$M_u=M_{l_u}\cup\{f_{r_u}\},$$

so root[u] is made by copying root[left] and adding $1$ at position rank[right].

To compare two segment-tree roots, find the largest rank where their counts differ. The larger count there means the larger function.

A persistent segment tree lets us do each insertion and comparison in $O(\log n)$.

To quickly know whether two subtrees differ while searching, store randomized 64-bit hashes in segment-tree nodes. The code below uses two hashes, because one hash is fine, two hashes is “please do not make me debug a cosmic ray” fine.

Tie-Breaking

If two functions are equal, the problem wants smaller index first.

The priority queue handles that directly: when two nodes have the same represented multiset, compare their indices.

When popping nodes, consecutive equal functions receive the same rank. Otherwise, the rank increases.

Complexity

Each internal node does one persistent segment tree insertion: $O(\log n)$.

Each priority queue comparison costs $O(\log n)$, and there are $O(n\log n)$ priority queue operations/comparisons overall.

So the total complexity is

$$O(n\log^2 n)$$

per test case, with $O(n\log n)$ memory for the persistent segment tree.

The sum of $n$ is $4\cdot 10^5$, so this passes comfortably.