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) ```

第一行包含一个整数 $T~(1 \le T \le 10^6)$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10 ^ 5)$。接下来的 $n-1$ 行中的每一行包含两个整数 $x$ 和 $y$，表示节点 $x$ 是节点 $y$ 的父节点（$1\le x, y\le n$）。这些边形成了一棵以 $1$ 为根的树。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $n$ 行。第 $i$ 行包含两个整数，表示节点 $i$ 在深度优先搜索顺序中出现的最小和最大位置。

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