CF2135F.To the Infinity

给定一棵有 $n$ 个结点的满二叉树$^{∗}$，根结点为 $1$。对于每个结点 $u$（$1\le u\le n$），定义函数 $f_u : \mathbb R_+ \to \mathbb R_+$ 如下：

• 如果 $u$ 是叶子$^{†}$，则 $f_u(x)=x$；
• 否则，设 $u$ 的左儿子为 $l_u$、右儿子为 $r_u$，则 $f_u(x)=(f_{l_u}(x))^{f_{r_u}(x)}$。

对于两个结点 $u$ 和 $v$，若且仅若下列条件之一成立，则认为 $u\prec v$：

• 当 $x\to\infty$ 时，$f_u(x)\lt f_v(x)$；
• 当 $x\to\infty$ 时，$f_u(x)=f_v(x)$ 并且 $u\lt v$。

可以证明，对于任意两个不同的结点 $u$ 和 $v$，总有 $u\prec v$ 或 $v\prec u$。

你需要按 $\prec$ 的顺序对所有结点进行排序。形式上，你需要找到一个长度为 $n$ 的排列$^{\text{§}}$ $p$，使得对每个 $1\le i\lt n$，都有 $p_i\prec p_{i+1}$。

$^{∗}$ 满二叉树是一种有根树，其中每个结点要么没有儿子，要么正好有 $2$ 个儿子。

$^{†}$ 叶子为没有儿子的结点。

$^{‡}$ 这里 $f_u(x)\lt f_v(x)$ 当 $x\to\infty$ 的定义是：存在一个正数 $N$，使得对所有 $x>N$，$f_u(x)\lt f_v(x)$ 恒成立。$f_u(x)=f_v(x)$ 也作同样定义。

$^{\text{§}}$ 长度为 $n$ 的排列是一个包含 $n$ 个互不相同的 $1$ 到 $n$ 的整数的数组。例如，$[2,3,1,5,4]$ 是一个排列；$[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组测试数据第一行为一个整数 $n$（$1\le n \le 4\cdot 10^5$，$n$ 是奇数），表示满二叉树的结点数。

接下来 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$0\le l_i, r_i\le n$），表示结点 $i$ 的左儿子和右儿子。如果 $i$ 是叶子，则 $l_i=r_i=0$。保证输入一定是一棵以 $1$ 为根的满二叉树。

保证所有测试数据中 $n$ 之和不超过 $4\cdot 10^5$。

对于每组测试数据，输出 $n$ 个整数 $p_1,p_2,\ldots,p_n$（$1\le p_i\le n$, 且所有 $p_i$ 互不相同），表示你找到的排列。你需要保证对每个 $1\le i\lt n$，都有 $p_i\prec p_{i+1}$。

在第一个测试样例中，$f_2(x)=f_3(x)=x$，$f_1(x)=(f_2(x))^{f_3(x)}=x^x$。当 $x\to\infty$ 时，显然 $f_2(x)=f_3(x)\lt f_1(x)$。因此，$2\prec 3\prec 1$。

在第二个测试样例中，$f_3(x)=f_4(x)=f_5(x)=x$，$f_2(x)=(f_4(x))^{f_5(x)}=x^x$，$f_1(x)=(f_2(x))^{f_3(x)}=x^{x^2}$。很显然，当 $x\to\infty$ 时 $x\lt x^2$，即 $f_2(x)\lt f_1(x)$。同理，$f_3(x)=f_4(x)=f_5(x)\lt f_2(x)\lt f_1(x)$。因此，$3\prec 4\prec 5\prec 2\prec 1$。

由 ChatGPT 5 翻译