P9872 [EC Final 2021] DFS Order

庞教授有一棵以 $1$ 为根的树，这棵树有 $n$ 个节点。这 $n$ 个节点的编号从 $1$ 到 $n$。 现在他想从根节点开始进行深度优先搜索。他想知道对于每个节点 $v$，它在深度优先搜索顺序中出现的最小和最大位置。深度优先搜索顺序是指在深度优先搜索过程中访问节点的顺序。一个节点出现在这个顺序中的第 $j$ 个位置（$1 \le j \le n$）意味着它是在 $j-1$ 个其他节点之后被访问的。由于一个节点的子节点可以以任意顺序进行迭代，因此存在多种可能的深度优先顺序。庞教授想知道对于每个节点 $v$，使得 $v$ 出现在第 $j$ 个位置的最小值和最大值分别是多少。 以下是对根树进行深度优先搜索的伪代码。在其执行之后，\texttt{dfs\_order} 是深度优先搜索顺序。 ``` let dfs_order be an empty list def dfs(vertex x): append x to the end of dfs_order. for (each son y of x): // sons can be iterated in arbitrary order. dfs(y) dfs(root) ```

无

无

题面翻译由 ChatGPT-4o 提供。