P17164 [CEOI 2026] DFS
题目描述
你可能已经熟悉著名的 DFS（深度优先搜索）图遍历算法。本题只考虑连通无向简单图（不含自环和重边），其顶点编号为 $0,1,\ldots,n-1$。DFS 算法按如下方式输出深度和顶点：
```
DFS(d, v):
output d/v
mark vertex v as visited
W = the list of neighbors of v ordered by increasing numbers
for each w in W:
if vertex w has not yet been visited:
DFS(d + 1, w)
```
编写一个程序，输出满足如下条件的不同图的数量：调用 DFS($0$, $n-1$) 时，其输出与输入给定的输出完全相同。例如，输出
$0/2$
$1/0$
$2/1$
可以由以下两个连通无向简单 $3$ 顶点图中的任意一个调用 DFS($0$, $2$) 得到：
:::align{center}
:::
输入格式
输入内容是对某个未知的 $n$ 顶点连通无向简单图调用 DFS($0$, $n-1$) 所得到的输出。因此，输入共包含 $n$ 行，每行格式为 $d/v$，第一行为 $0/(n-1)$。
输出格式
输出满足要求的不同图的数量。由于答案可能非常大，请输出其对 $1\,000\,000\,007$ 取模后的结果。
说明/提示
### 限制条件
- $1\le n\le 2\cdot 10^5$
### 子任务
- 子任务 $1$（$10$ 分）：$n\le 6$。
- 子任务 $2$（$20$ 分）：$n\le 500$。
- 子任务 $3$（$20$ 分）：$n\le 10^4$。
- 子任务 $4$（$10$ 分）：对于每个 $i\in\{2,\ldots,n\}$，输入的第 $i$ 行均为 $(i-1)/(i-2)$。
- 子任务 $5$（$20$ 分）：对于每个 $i\in\{2,\ldots,n\}$，输入的第 $i$ 行均为 $(i-1)/v$，其中某个 $v\in\{0,\ldots,n-2\}$。
- 子任务 $6$（$20$ 分）：无额外限制。
翻译由 ChatGPT-5.6 完成