#P18878. [2026多校联测]深搜

[2026多校联测]深搜

深搜

题目描述

对于一个有根树,我们记 f(v)f(v) 为对以 vv 为根的子树 dfs(可以以任意顺序访问儿子)能够得到的本质不同的“节点遍历序列去除非前缀最大值后形成的序列”的数量对 109+710^{9} + 7 取模后的结果。

给定一个 nn 个点的,下标从 11 开始且以 rr 为根的树。

当 o=1o = 1 时,请求出 f(r)f(r);

当 o=2o = 2 时,请求出 f(1),f(2),…,f(n)f(1),f(2),\dots,f(n)。

输入格式

第一行三个正整数 id,o,tid,o,t,其中 idid 表示测试点编号(特别地,样例中 id=0id = 0),tt 表示数据组数。

对于每组数据:

第一行两个正整数 n,rn,r。

接下来 n−1n-1 行,每行两个正整数 u,vu,v 表示树上一条边的两个端点。

输出格式

对于每组数据输出一行:

若 o=1o = 1,输出一个非负整数 f(r)f(r);

若 o=2o = 2,输出 nn 个非负整数 f(1),f(2),…,f(n)f(1),f(2),\dots,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

说明/提示

样例 11 解释

第三组数据中 f(1)=2f(1) = 2,本质不同的序列如下:

  1. [1,3][1,3];
  2. [1,2,3][1,2,3]。

第五组数据中 f(1)=8f(1) = 8,本质不同的序列如下:

  1. [1,5][1,5];
  2. [1,2,5][1,2,5];
  3. [1,3,5][1,3,5];
  4. [1,4,5][1,4,5];
  5. [1,2,3,5][1,2,3,5];
  6. [1,2,4,5][1,2,4,5];
  7. [1,3,4,5][1,3,4,5];
  8. [1,2,3,4,5][1,2,3,4,5]。

第六组数据中 f(1)=6f(1) = 6,本质不同的序列如下:

  1. [1,4,9,10][1,4,9,10];
  2. [1,4,7,9,10][1,4,7,9,10];
  3. [1,2,5,8,9,10][1,2,5,8,9,10];
  4. [1,2,6,8,9,10][1,2,6,8,9,10];
  5. [1,2,3,5,8,9,10][1,2,3,5,8,9,10];
  6. [1,2,3,6,8,9,10][1,2,3,6,8,9,10]。

样例 2∼112 \sim 11

见附加样例。

样例 2,32,3 满足 n≤8,∑n≤8×103n \leq 8, \sum n \leq 8 \times 10^{3};

样例 4,54,5 满足 n≤14,∑n≤1.4×104n \leq 14, \sum n \leq 1.4 \times 10^{4};

样例 6,76,7 满足 $n \leq 3 \times 10^{3}, \sum n \leq 3 \times 10^{4}$;

样例 8,98,9 满足 $n \leq 1.5 \times 10^{5}, \sum n \leq 6 \times 10^{5}$;

样例 10,1110,11 满足 $n \leq 5 \times 10^{5}, \sum n \leq 2 \times 10^{6}$;

此外,样例 2∼112 \sim 11 满足:编号为奇数的样例中,o=1o = 1;编号为偶数的样例中,o=2o = 2。编号为奇数的样例输入与编号为偶数的样例输入在忽略 oo 的不同后是完全一致的。并且,这些样例中的树与具有特殊性质 B\text{B} 的正式测试点强度相同。

数据规模与约定

测试点编号 n≤n \leq ∑n≤\sum n \leq o=o = 特殊性质
11 88 8×1038 \times 10^{3} 22 A\text{A}
22 1111 1.1×1041.1 \times 10^{4}
33 1414 1.4×1041.4 \times 10^{4}
44 1717 1.7×1041.7 \times 10^{4}
5∼75 \sim 7 3×1033 \times 10^{3} 3×1043 \times 10^{4} 11
8,98,9 22
10∼1410 \sim 14 1.5×1051.5 \times 10^{5} 6×1056 \times 10^{5} 11 无
15,1615,16 22 B\text{B}
17,1817,18 无
19∼2119 \sim 21 5×1055 \times 10^{5} 2×1062 \times 10^{6} 11
2222 22 C\text{C}
2323 D\text{D}
24,2524,25 无

特殊性质 A\text{A}:t≤103t \leq 10^{3};

特殊性质 B\text{B}:树的形态随机;

特殊性质 C\text{C}:将树视作无根树后,树是链;

特殊性质 D\text{D}:将树视作无根树后,树是菊花图。

树的形态随机过程如下:对于 i=2,3,…,ni = 2,3,\dots,n,取 fi=RAND(1,i−1)f_{i} = \text{RAND}(1,i-1),然后在 fif_{i} 和 ii 之间连边,最后按照特定方式重新分配点编号(你无需关心编号分配方式)。注意:点的编号不是随机分配的。

对于所有数据,$o \in \{1,2\},t \leq 10^{4},n \leq 5 \times 10^{5}, \sum n \leq 2 \times 10^{6}$。

本题输入量和输出量均较大,请使用快速输入输出。下发文件中提供了一份快速输入输出整数的模板(fastio.cpp)。