P15108 白井黑子

这是一道交互题。 请勿使用 C++14 (GCC 9) 提交。 此题是黑子测试你是否具有空间系超能力而制作的。

给定一棵以 $1$ 为根有根树，标号 $1$ 到 $n$，求这棵树的 DFS 序。 具体地，有如下伪代码： ```cpp int d[n], tot = 0 set son[n] void dfs(int u): d[tot] = u tot += 1 for v in son[u]: // in any order dfs(v) dfs(1) ``` $d$ 数组即为所求。 显然，一棵树可以有多个 DFS 序，你只要求出任意一个即可。 ### 交互方式 我们定义了类型 `Array` 表示长度 $n$，值域 $[0,n]$ 的数组。你可以调用它的两个方法： 1. `int operator[](int x)`，表示获取该数组第 $x$ 位的值。必须满足 $x\in[0,n]$。 2. `void set(int x,int y)`，表示将数组第 $x$ 位设置为 $y$。必须满足 $x\in [0,n]$ 以及 $y\in[0,n]$。调用 `a.set(x,y)` 后，$a[x]$ 将返回 $y$。 所有方法的复杂度均为 $O(1)$。 你需要编写一个函数 `void dfs(int n, Array &f,Array &a)`。其中 $f[i]$ 的初始值为点 $i$ 的父亲，这里规定根的父亲为 $0$，且 $f[0]=0$；$a[i]$ 初始值全部为 $0$。 该函数会被调用恰好一次。你需要在函数返回时，在 $a$ 中写入你求出的 DFS 序。具体地，对于每一个 $i\in [1,n]$，最后一次调用 `a.set(i,x)` 的 $x$ 需为 DFS 序的第 $x$ 项，$a[0]$ 的值没有要求。 另外，你还可以调用函数 `int fa(int x)`，它返回 $f[x]$ 的初始值（$x$ 的父亲），要求 $x\in[0,n]$。注意，如果调用了该函数，仅能获得当前测试点 $50\%$ 的分数。 **本题实际的空间限制为 1MB，多余空间将由交互器消耗。需要注意的是，递归函数消耗的栈空间也计入空间限制。** 请注意，任何绕过提供的方法而直接使用传入的类型空间的行为被视为攻击交互器，将会被判为 $0$ 分。 下发文件中提供了 `dfs.cpp`，你可以在此程序的基础上编写代码。该代码已内置交互器，可以直接测试样例以及提交。你只需要完善其中的 `dfs` 函数。

以下是提供给示例交互器的输入格式： 第一行，一个正整数 $n$。 接下来一行 $n-1$ 个整数，表示 $2\sim n$ 号结点的父亲。

以下是提供给示例交互器的输出格式： 一行 $n$ 个整数，表示选手代码返回的 DFS 序。

**本题采用捆绑测试。** - Subtask 1（20 pts）：$n\le 10^5$，时限 1s。 - Subtask 2（30 pts）：$n\le 10^6$，时限 6s。 - Subtask 3（30 pts）：$n\le 5\times 10^6$，时限 6s。 - Subtask 4（10 pts）：对于 $i\ge 1$，初始有 $f[i]