#P9479. [NOI2023] 桂花树

[NOI2023] 桂花树

题目描述

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

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

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

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

输入格式

本题有多组测试数据。

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

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

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

输入的第二行包含 n1n-1 个整数 f2,f3,,fnf_2,f_3,\dots,f_n,其中 fif_i 表示 TT 中节点 ii 的父亲节点编号。

输出格式

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

0 3
1 2 1

2 2 1
1
2 2 0
1
3
16
15
见附件中的 tree/tree2.in。
见附件中的 tree/tree2.ans。
见附件中的 tree/tree3.in。
见附件中的 tree/tree3.ans。
见附件中的 tree/tree4.in。
见附件中的 tree/tree4.ans。

提示

【样例解释 #1】

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

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

【样例解释 #2】

该组样例满足 n100n \le 100,五组测试数据中 mm 分别不超过 0,1,1,2,20, 1, 1, 2, 2

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

对于所有测试数据保证:1t151 \le t \le 151n3×1041 \le n \le 3 \times 10^40m30000 \le m \le 30000k100 \le k \le 101fii11 \le f_i \le i - 1

测试点编号 nn \le mm \le kk \le
1,21,2 44 1010
33 3×1043\times 10^4 00
44 10210^2 11
55 3×1043 \times 10^4
66 10210^2 22
77 3×1043\times 10^4
8,98,9 11 10210^2 00
1010 3,0003,000
1111 10210^2 1010
1212 3,0003,000
13,1413,14 10210^2 00
15,1615,16 3×1043\times 10^4 3,0003,000
17,1817,18 10210^2 1010
19,2019,20 3×1043\times 10^4 3,0003,000