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

第一行包含一个整数 $n(1\le n\le 5\times 10^5)$，表示这棵树的顶点数。 接下来一行包含 $n$ 个数字，第 $i$ 个数字是 $p_i(1\le p_i\le n)$。保证 $p_1,p_2,\dots,p_n$ 是 $1,2,3\dots,n$ 的一个排列。 接下来的 $n-1$ 行描述了树的边。第 $i$ 行包含两个整数 $u_i$ 和 $v_i(1\le u_i,v_i\le n)$，表示第 $i$ 条边连接的顶点编号。 保证给定的边构成一棵树。 并且对于任意顶点 $x

输出 $n$ 个整数，表示 $\{a_n\}$ 的最小字典序。

（由 ChatGPT 4o 翻译）