P15108 白井黑子
考虑首先你应当要能在树上遍历，因此我们需要有一个邻接表，考虑用 \(a_u\) 存 \(u\) 的第一个儿子，\(f_u\) 存 \(u\) 的一个兄弟（不存在都设为 0）。容易遍历一遍 \(f\) 数组构建出该邻接表。
接下来考虑在树上 dfs，如果允许使用 \(fa(u)\) 函数的话是简单的：
- 设当前点 \(u\)。
- 如果 \(a_u\) 不为 \(0\) 就令 \(u\leftarrow a_u\)。
- 如果 \(a_u\) 为 \(0\) 且 \(f_u\) 不为 \(0\) 就令 \(u\leftarrow f_u\)；否则就不断跳父亲 \(fa(u)\) 直到 \(f_u\) 存在。
可以用 \(a_u\) 存储 \(u\) 被遍历的时间，然后就可以求出 DFS 序了。
如果不允许使用 \(fa(u)\)，我们考虑在每个点的最后一个儿子的 \(f_u\) 设为 \(fa(u)\)，然后接下来我们希望用 \(a_u\) 来表示 \(u\) 在 DFS 序上的下一个点是 \(a_u\)，即把所有点串起来。
另外，我们需要区分 \(f_u\) 表示的是 \(u\) 的兄弟还是父亲，这个只需要判断 \(f_u\) 是否遍历过。我们可以当每次沿着 \(f_u\) 走过之后，将 \(f_u\) 变成 \(0\)。这样，如果 \(a_u=0\)（\(u\) 是叶子）或者 \(f_{a_u}\neq 0\)，我们就可以知道 \(u\) 没有访问过。
最后遍历 \(a_u\) 得到 DFS 序即可。