题意简述

我们有一棵 $n$ 个节点的满二叉树（每个节点要么是叶子，要么有两个孩子）。
对每个节点 $u$，定义函数 $f_u(x)$：

• 若 $u$ 是叶子：$f_u(x) = x$
• 否则，设左孩子 $l_u$，右孩子 $r_u$：$$f_u(x) = \big(f_{l_u}(x)\big)^{f_{r_u}(x)}$$

对两个节点 $u,v$，定义偏序 $u \prec v$：

1. 若 $\lim_{x\to\infty} \frac{f_u(x)}{f_v(x)} = 0$，则 $u \prec v$（即 $f_u(x) < f_v(x)$ 当 $x$ 充分大时）。
2. 若 $\lim_{x\to\infty} \frac{f_u(x)}{f_v(x)} = 1$ 且 $u < v$，则 $u \prec v$。

已知对所有不同的 $u,v$，要么 $u \prec v$ 要么 $v \prec u$。
要求输出按 $\prec$ 升序排列的节点编号。

---

1. 函数结构与“幂塔”

函数 $f_u(x)$ 的形式是：

• 叶子：$x$
• 内部节点：$x$ 的“幂塔”形式，例如 $x^{x^{x}}$ 或更复杂的指数塔。

实际上，对于每个节点 $u$，$f_u(x)$ 可以唯一表示为：

$$f_u(x) = x^{\,T_1^{\,T_2^{\,\cdots^{\,T_m}}}}$$

其中 $T_1, T_2, \dots, T_m$ 也是类似形式的幂塔，并且 $m$ 是常数（与 $x$ 无关）。
更形式化地，幂塔定义为：

• $x$ 本身是幂塔。
• 若 $X_1, X_2, \dots, X_m$ 是幂塔，则 $x^{X_1^{X_2^{\cdots^{X_m}}}}$ 也是幂塔。

这里注意，指数部分是从上往下运算的，即 $a^{b^c} = a^{(b^c)}$，不是 $(a^b)^c$。

---

2. 比较幂塔的大小（当 $x \to \infty$）

比较两个幂塔 $X = x^{A_1^{A_2^{\cdots}}}$ 和 $Y = x^{B_1^{B_2^{\cdots}}}$ 的大小：

• 如果其中一个就是 $x$（即 $A_1$ 不存在），直接比较。
• 否则，比较 $A_1, A_2, \dots$ 和 $B_1, B_2, \dots$ 的字典序（从第一个指数开始比较）。

但注意：指数运算不是交换的，所以不能直接比较指数列表。实际上，幂塔的比较等价于：
把指数部分看作一个序列 $E_1, E_2, \dots, E_m$，按从顶到底的顺序比较，但需要先对每个节点的指数序列进行降序排序。

为什么？因为 $x^{a^{b}} = x^{b^{a}}$ 吗？不成立，$a^{b} \neq b^{a}$ 一般。
但关键是：对于足够大的 $x$，比较 $x^{P}$ 和 $x^{Q}$ 等价于比较 $P$ 和 $Q$（因为 $x^a > x^b$ 当且仅当 $a > b$，对 $x>1$ 成立）。
而 $P$ 本身也是幂塔，所以比较递归进行。

更关键的是：在幂塔 $x^{T_1^{T_2^{\cdots}}}$ 中，指数部分 $T_1^{T_2^{\cdots}}$ 的排序规则是：
先对 $T_1, T_2, \dots$ 按降序排，然后比较字典序。
这等价于：把 $f_u(x)$ 对应的指数塔序列（从最外层指数往下）排序后比较。

---

3. 树上的性质

对于节点 $u$，设它的左右孩子 $l_u, r_u$，则

$$f_u(x) = \big(f_{l_u}(x)\big)^{f_{r_u}(x)}$$

这是 $x^{(\text{左指数塔})^{(\text{右指数塔})}}$ 的形式吗？不，注意括号：
$(f_{l_u}(x))^{f_{r_u}(x)}$ 并不是 $x$ 为底，除非 $f_{l_u}(x) = x$。

但我们可以递归定义：
每个 $f_u(x)$ 的标准形式是 $x$ 的幂塔。
例如，如果 $f_{l_u}(x) = x^{A}$，$f_{r_u}(x) = x^{B}$，那么

$$f_u(x) = (x^{A})^{x^{B}} = x^{A \cdot x^{B}}$$

这不再是简单的 $x$ 的幂塔（因为指数中有 $x^{B}$ 与 $A$ 相乘）。
所以上面的“幂塔”定义需要修改：实际比较时，我们真正需要的是指数塔的递归比较，而这里的 $f_u(x)$ 严格来说是指数塔的“乘积”形式，但可以通过重写为 $x$ 的幂塔来统一。

---

4. 比较算法的关键

比较 $f_u(x)$ 和 $f_v(x)$ 的大小时，我们只需要知道它们指数塔的字典序。
每个节点 $u$ 的指数塔序列可以通过后序遍历构造：

• 叶子：序列为空（即 $f_u(x) = x$）。
• 内部节点 $u$：设左孩子 $l_u$ 的指数塔序列为 $L_1, L_2, \dots$，右孩子 $r_u$ 的指数塔序列为 $R_1, R_2, \dots$。
  那么 $f_u(x) = x^{\,L_1^{\,L_2^{\cdots}} \cdot x^{\,R_1^{\,R_2^{\cdots}}}}$
  这其实等价于 $x^{\,L_1^{\,L_2^{\cdots}} \,+\, \log_x(\cdots)}$，形式复杂。

但题解中用了一种更简单的方法：
每个节点的 $f_u(x)$ 可以唯一编码成一个哈希值，并且比较两个节点时，通过比较它们指数塔的排序后序列的哈希来决定大小。

---

5. 标程的解法

5.1 拓扑序与堆

• 用 d[u] 表示节点 $u$ 的未处理孩子数。初始时，叶子节点的 $d[u]=0$。
• 将所有叶子入堆（最小堆，按 $f_u(x)$ 大小排序）。
• 每次弹出堆顶 $u$，输出 $u$（这就是当前最小的节点）。
• 若 $u$ 的父节点 $fa[u]$ 的 $d$ 减到 $0$，说明它的两个孩子都处理完了，可以计算 $f_{fa[u]}(x)$ 的哈希，并将父节点入堆。

这样输出的顺序就是 $u_1 \prec u_2 \prec \dots$。

---

5.2 比较函数（堆的排序依据）

我们需要比较两个节点 $x$ 和 $y$ 的 $f(x)$ 大小。

关键：每个 $f_u(x)$ 对应一个指数塔序列，比较时先对序列降序排序，再比较字典序。

标程中用持久化线段树来维护这个排序后的序列的哈希：

• 每个节点 $u$ 的序列：把它的两个孩子 $l_u, r_u$ 的序列合并，然后降序排序，得到新序列。
• 如何快速比较两个序列？
  用持久化线段树存序列的哈希值，支持：
  • add(rt[u], rt[l[u]], 1, n, rk[r[u]], shift(h[r[u]]))
    表示把右孩子的哈希插入到左孩子序列的适当位置（按排序顺序）。
  • find(rt[x], rt[y], 1, n) 用于比较两个序列的字典序：
    从右到左（即从大到小）找第一个不同的位置，返回谁更大。

这样比较两个节点 $x, y$ 的 $f$ 大小是 $O(\log n)$。

---

5.3 哈希与排序顺序

• h[u] 是 $u$ 的哈希值，用于快速判断相等。
• 当两个节点的 $h$ 相等时，比较编号 $u < v$ 决定顺序（题目规则 2）。
• 否则，通过 find(rt[x], rt[y]) 比较。

---

5.4 更新父节点

当 $u$ 的两个孩子都处理完后（即 $d[fa[u]]$ 变为 $0$），调用 upd(fa[u])：

void upd(int u) {
    h[u] = h[l[u]] + shift(h[r[u]]);
    add(rt[u], rt[l[u]], 1, n, rk[r[u]], shift(h[r[u]]));
}

这里：

• h[u] 的计算是简单的组合哈希。
• add 把右孩子的哈希值插入到左孩子序列的适当位置，得到 $u$ 的序列。

rk[r[u]] 是右孩子在其父节点序列中的排序位置（由 tot 递增赋予，表示不同的哈希值对应的排名）。
这样，序列被压缩成排名，便于比较。

---

6. 复杂度

• 每个节点入堆一次，出堆一次，$O(n \log n)$。
• 每次比较 $O(\log n)$（线段树深度）。
• 每次更新 $O(\log n)$（插入到持久化线段树）。
• 总 $O(n \log^2 n)$。

---

7. 总结

题解的核心：

1. 将 $f_u(x)$ 抽象为指数塔序列。
2. 比较两个 $f_u(x)$ 的大小等价于比较它们排序后的指数塔序列的字典序。
3. 用拓扑排序 + 堆，每次处理当前最小的节点。
4. 用持久化线段树维护每个节点的排序后序列的哈希，支持 $O(\log n)$ 比较和更新。

这样就能在 $O(n \log^2 n)$ 内求出所有节点的 $\prec$ 顺序。