深搜
题目描述
对于一个有根树,我们记 f(v) 为对以 v 为根的子树 dfs(可以以任意顺序访问儿子)能够得到的本质不同的“节点遍历序列去除非前缀最大值后形成的序列”的数量对 109+7 取模后的结果。
给定一个 n 个点的,下标从 1 开始且以 r 为根的树。
当 o=1 时,请求出 f(r);
当 o=2 时,请求出 f(1),f(2),…,f(n)。
输入格式
第一行三个正整数 id,o,t,其中 id 表示测试点编号(特别地,样例中 id=0),t 表示数据组数。
对于每组数据:
第一行两个正整数 n,r。
接下来 n−1 行,每行两个正整数 u,v 表示树上一条边的两个端点。
输出格式
对于每组数据输出一行:
若 o=1,输出一个非负整数 f(r);
若 o=2,输出 n 个非负整数 f(1),f(2),…,f(n)。
输入输出样例 #1
0 2 6
1 1
2 1
1 2
3 1
1 2
1 3
3 1
1 2
2 3
5 1
1 2
1 3
1 4
1 5
10 1
1 2
2 3
1 4
2 5
2 6
4 7
5 8
4 9
9 10
1
1 1
2 1 1
1 1 1
8 1 1 1 1
6 4 1 2 1 1 1 1 1 1
说明/提示
样例 1 解释
第三组数据中 f(1)=2,本质不同的序列如下:
- [1,3];
- [1,2,3]。
第五组数据中 f(1)=8,本质不同的序列如下:
- [1,5];
- [1,2,5];
- [1,3,5];
- [1,4,5];
- [1,2,3,5];
- [1,2,4,5];
- [1,3,4,5];
- [1,2,3,4,5]。
第六组数据中 f(1)=6,本质不同的序列如下:
- [1,4,9,10];
- [1,4,7,9,10];
- [1,2,5,8,9,10];
- [1,2,6,8,9,10];
- [1,2,3,5,8,9,10];
- [1,2,3,6,8,9,10]。
样例 2∼11
见附加样例。
样例 2,3 满足 n≤8,∑n≤8×103;
样例 4,5 满足 n≤14,∑n≤1.4×104;
样例 6,7 满足 $n \leq 3 \times 10^{3}, \sum n \leq 3 \times 10^{4}$;
样例 8,9 满足 $n \leq 1.5 \times 10^{5}, \sum n \leq 6 \times 10^{5}$;
样例 10,11 满足 $n \leq 5 \times 10^{5}, \sum n \leq 2 \times 10^{6}$;
此外,样例 2∼11 满足:编号为奇数的样例中,o=1;编号为偶数的样例中,o=2。编号为奇数的样例输入与编号为偶数的样例输入在忽略 o 的不同后是完全一致的。并且,这些样例中的树与具有特殊性质 B 的正式测试点强度相同。
数据规模与约定
| 测试点编号 |
n≤ |
∑n≤ |
o= |
特殊性质 |
| 1 |
8 |
8×103 |
2 |
A |
| 2 |
11 |
1.1×104 |
| 3 |
14 |
1.4×104 |
| 4 |
17 |
1.7×104 |
| 5∼7 |
3×103 |
3×104 |
1 |
| 8,9 |
2 |
| 10∼14 |
1.5×105 |
6×105 |
1 |
无 |
| 15,16 |
2 |
B |
| 17,18 |
无 |
| 19∼21 |
5×105 |
2×106 |
1 |
| 22 |
2 |
C |
| 23 |
D |
| 24,25 |
无 |
特殊性质 A:t≤103;
特殊性质 B:树的形态随机;
特殊性质 C:将树视作无根树后,树是链;
特殊性质 D:将树视作无根树后,树是菊花图。
树的形态随机过程如下:对于 i=2,3,…,n,取 fi=RAND(1,i−1),然后在 fi 和 i 之间连边,最后按照特定方式重新分配点编号(你无需关心编号分配方式)。注意:点的编号不是随机分配的。
对于所有数据,$o \in \{1,2\},t \leq 10^{4},n \leq 5 \times 10^{5}, \sum n \leq 2 \times 10^{6}$。
本题输入量和输出量均较大,请使用快速输入输出。下发文件中提供了一份快速输入输出整数的模板(fastio.cpp)。