Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#271. [NOI2023] 桂花树

Statistics

下发文件:http://119.27.163.117/download.php?type=problem&id=271

题目描述

小 B 八年前看到的桂花树是一棵 $n$ 个节点的树 $T$,保证 $T$ 的非根结点的父亲的编号小于自己。给定整数 $k$,称一棵 $(n+m)$ 个节点的有根树 $T^{\prime}$ 是繁荣的,当且仅当以下所有条件满足:

  1. 对于任意满足 $1 \le i,j \le n$ 的 $(i,j)$,在树 $T$ 和树 $T^{\prime}$ 上,节点 $i$ 和 $j$ 的最近公共祖先编号相同。
  2. 对于任意满足 $1 \le i,j \le n + m$ 的 $(i,j)$,在树 $T^{\prime}$ 上,节点 $i$ 和 $j$ 的最近公共祖先编号不超过 $\max(i,j)+k$。

注意题目中所有树的节点均从 $1$ 开始编号,且根结点编号为 $1$。$T^{\prime}$ 不需要满足非根结点的父亲编号小于自己。

小 B 想知道有多少棵 $(n+m)$ 个节点的树是繁荣的,认为两棵树不同当且仅当存在某一个节点在两棵树上的父亲不同。你只输出方案数在模 $(10^9+7)$ 意义下的值。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c,t$,分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据,对于每组测试数据:

输入的第一行包含三个整数 $n,m,k$。

输入的第二行包含 $n-1$ 个整数 $f_2,f_2,\dots,f_n$,其中 $f_i$ 表示 $T$ 中节点 $i$ 的父亲节点编号。

输出格式

对于每组测试数据输出一行一个整数,表示繁荣的树的数量在模 $(10^9+7)$ 意义下的答案。

样例 #1

样例输入 #1

0 3
1 2 1

2 2 1
1
2 2 0
1

样例输出 #1

3
16
15

样例 #2

样例输入 #2

见附件中的 tree/tree2.in。

样例输出 #2

见附件中的 tree/tree2.ans。

样例 #3

样例输入 #3

见附件中的 tree/tree3.in。

样例输出 #3

见附件中的 tree/tree3.ans。

样例 #4

样例输入 #4

见附件中的 tree/tree4.in。

样例输出 #4

见附件中的 tree/tree4.ans。

提示

【样例解释 #1】

对于样例中的第一组测试数据,有三棵合法的树,其每个节点的的父亲构成的序列 $\{f_2,f_3\}$ 分别为 $\{1,1\}$、$\{3,1\}$、$\{1,2\}$。注意这组测试数据的第二行为空行。

对于样例中的第二组、第三组测试数据,共有 $16$ 棵树满足第一个条件,其中只有父亲序列为 $\{4,4,1\}$ 的树在第三组测试数据中不满足第二个条件。

【样例解释 #2】

该组样例满足 $n \le 100$,五组测试数据中 $m$ 分别不超过 $0, 1, 1, 2, 2$。

【样例解释 #3】

该组样例满足 $k = 0$,五组测试数据中前两组测试数据满足 $n = 1$,第一、三、四组测试数据满足 $n, m \le 100$。

【样例解释 #4】

该组样例前两组测试数据满足 $n = 1$,第一、三、四组测试数据满足 $n, m \le 100$。

【数据范围】

对于所有测试数据保证:$1 \le t \le 15$,$1 \le n \le 3 \times 10^4$,$0 \le m \le 3000$,$0 \le k \le 10$,$1 \le f_i \le i - 1$。

测试点编号 $n \le$ $m \le $ $k \le $
$1,2$ $4$ $4$ $10$
$3$ $3\times 10^4$ $0$ $10$
$4$ $10^2$ $1$ $10$
$5$ $3 \times 10^4$ $1$ $10$
$6$ $10^2$ $2$ $10$
$7$ $3\times 10^4$ $2$ $10$
$8,9$ $1$ $10^2$ $0$
$10$ $1$ $3,000$ $0$
$11$ $1$ $10^2$ $10$
$12$ $1$ $3,000$ $10$
$13,14$ $10^2$ $10^2$ $0$
$15,16$ $3\times 10^4$ $3,000$ $0$
$17,18$ $10^2$ $10^2$ $10$
$19,20$ $3\times 10^4$ $3,000$ $10$