P10560 [ICPC 2024 Xi'an I] Holes and Balls

给定 $n$ 个球，第 $i$ 个球的值为 $p_i$。保证 $p_1,p_2,\dots,p_n$ 是 $1,2,3\dots,n$ 的一个排列。 有一棵有根树，包含 $n$ 个顶点，每个顶点是一个洞，每个洞只能容纳一个球。 树的根是第一个顶点。 现在你需要用这些球填满洞。 你需要按 $1$ 到 $n$ 的顺序依次投掷每个球，步骤如下： 1. 将球投到顶点 $1$。 2. 设球所在的顶点为 $p$。 3. 如果第 $p$ 个顶点已经被其他球填满，你需要选择一个顶点 $x$，将球投到第 $x$ 个顶点，然后返回步骤 $2$。你需要保证第 $x$ 个顶点是第 $p$ 个顶点的子节点，并且第 $x$ 个顶点的子树中至少有一个顶点未被填满。 4. 否则，球将填满第 $p$ 个顶点。 投完所有球后，用 $a_i$ 表示第 $i$ 个顶点中球的值。 你需要找到 $\{a_n\}$ 的最小字典序。 我们定义 $dep_i$ 为从第 $i$ 个顶点到树根（第一个顶点）的路径上的顶点数。 特别地，对于任意两个顶点 $x

无

无

（由 ChatGPT 4o 翻译）