CCF GESP 2025年6月认证 C++ 8级
题目描述
给定一棵有 $ n $ 个结点的有根树，结点依次以 $1,2,\dots,n$ 编号，其中根结点的编号为 $1$。
小 A 计划在这棵有根树上进行 $q$ 次旅行。在第 $i$ 次旅行中，小 A 首先选定结点 $s_i$ 作为起点，并移动若干次。移动分为以下两种：
- 移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
- 移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。
由于移动次数可能很大，对于第 $i$ 次旅行，旅行中的移动以 $k_i$ 个不为零的整数构成的序列 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ 表示。对 $a_{i,j}$，若 $a_{i,j} > 0$ 则代表进行 $a_{i,j}$ 次第一种移动；若 $a_{i,j} < 0$ 则代表进行 $-a_{i,j}$ 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。
输入格式
第一行，两个正整数 $n, q$，分别表示有根树的结点数量，以及旅行次数。
第二行，$n-1$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示结点 $i$ 的父结点编号。
接下来 $2q$ 行中的第 $2i-1$ 行（$1 \leq i \leq q$）包含两个正整数 $s_i, k_i$，分别表示第 $i$ 次旅行的起点编号，以及移动序列的长度。第 $2i$ 行包含 $k_i$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$，表示移动序列。
输出格式
输出共 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次旅行终点的结点编号。
样例说明
样例 1
5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 14
1
4
2样例 2
8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 81
7
1数据范围
对于所有测试点，保证：$1 \leq n \leq 10^5$， $1 \leq q \leq 2 \times 10^4$， $1 \leq p_i \leq n$， $1 \leq s_i \leq n$， $k_i \geq 1$ 且 $\sum k_i \leq 10^5$， $1 \leq |a_{i,j}| \leq n$。
题目描述
给定一棵有 $n$ 个结点的树 $T$，结点依次以 $1,2,\dots,n$ 标号。树 $T$ 的深度优先遍历序可由以下过程得到：
- 选定深度优先遍历的起点 $s$（$1 \leq s \leq n$），当前位置结点即是起点。
- 若当前结点存在未被遍历的相邻结点 $u$ 则遍历 $u$，也即令当前位置结点为 $u$ 并重复这一步；否则回溯。
- 按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。
第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序也是任意的，因此对于同一棵树 $T$ 可能有多组不同的深度优先遍历序。请你求出树 $T$ 有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对 $10^9$ 取模之后的结果。
输入格式
第一行，一个整数 $n$，表示树 $T$ 的结点数。
接下来 $n-1$ 行，每行两个正整数 $u_i, v_i$，表示树 $T$ 中的一条连接结点 $u_i, v_i$ 的边。
输出格式
输出一行，一个整数，表示树 $T$ 的不同的深度优先遍历序数量对 $10^9$ 取模的结果。
样例说明
样例 1
4
1 2
2 3
3 46样例 2
8
1 2
1 3
1 4
2 5
2 6
3 7
3 8112数据范围
对于 $40\%$ 的测试点，保证 $1 \leq n \leq 8$。
对于另外 $20\%$ 的测试点，保证给定的树是一条链。
对于所有测试点，保证 $1 \leq n \leq 10^5$。