P14107 [ZJCPC 2017] Binary Tree Restoring

给定一棵二叉树的两个深度优先搜索（DFS）序列，你能否找到一个同时满足这两个 DFS 序列的二叉树？ 回顾一下，二叉树是一种每个节点最多有两个子节点的树结构，深度优先搜索是一种遍历树的方式，从根节点开始，沿着树的分支尽可能深地遍历节点，然后再回溯。

输入包含多组测试数据。第一行为一个整数 $T$，表示测试数据组数。对于每一组测试数据： 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示二叉树的节点数量。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n$，对于所有 $1 \le i < j \le n$，$a_i \ne a_j$），表示二叉树的第一个 DFS 序列。 第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1 \le b_i \le n$，对于所有 $1 \le i < j \le n$，$b_i \ne b_j$），表示二叉树的第二个 DFS 序列。 保证所有测试数据中 $n$ 的总和不超过 $10^6$，且至少存在一种满足条件的二叉树。 温馨提示：本题数据量较大，建议使用更快的输入输出方式。例如，在 C++ 中可以使用 scanf/printf 替代 cin/cout。

对于每一组测试数据，输出一行，包含 $n$ 个整数，每两个整数之间用一个空格隔开。第 $i$ 个整数表示第 $i$ 个节点在所构造的二叉树中的父节点编号。如果第 $i$ 个节点是树的根节点，则父节点编号输出 $0$。如果有多组合法答案，你可以输出其中任意一种。 请注意，行末不得输出多余的空格，否则可能会导致“答案错误”的判定，因为本题为特殊判题。

由 ChatGPT 5 翻译