额外提供 $60\%$ 的时间。
小 P 有一棵包含 $n$ 个节点的有根树，这些节点的编号分别为 $1,2,3,…,n$。其中，节点 $1$ 为根节点，且对于所有满足 $2≤i≤n$ 的整数 $i$，节点 $i$ 的父亲节点为节点 $p[i]$。特别地，$p[1]=1$。
若节点 $i$ 有 $s[i]$ 个儿子节点，则按儿子节点的编号顺序，节点 $i$ 与儿子节点之间的边的权值依次为 $1,2,3,…,s[i]$。以下是对于 $p=[1,1,1,3,3]$ 的一个例子：
小 P 定义一棵树对于一个节点 $i$ 的路径可以用一个由根节点到节点 $i$ 的简单路径所经过的边的权值所组成的序列。例如，在上图中节点 $4$ 的路径就是序列 $[2,1]$。
小 P 找到了他的朋友小 Q，并打算用这棵树和他玩一个游戏。
游戏会进行 $m$ 轮，对于第 $i$ 轮：
- 小 P 会在他的树中找出根节点为 $r[i]$ 的一棵子树进行游戏。对于那棵子树，他会挑选一个节点 $a[i]$，并告诉小 Q 它的路径。记它的路径的长度是 $l[i]$。在这里，路径是对于该子树而言，与原来的树无关。
- 小 Q 会根据这条路径从节点 $r[i]$ 开始搜索。经过 $j$ 条边抵达一个节点时，他都会根据路径的第 $j+1$ 个元素选择边权与它相等的一条边，并走到那条边所对应的另一个节点。但小 Q 可能会选错边，在一轮游戏中，他最多可能选错 $k$ 条边。
- 如果小 Q 无法继续搜索 (即到达了子树的叶子节点、走过的边数超过 $l[i]$ 或没有边权与对应的路径元素相等的一条边)，他会回答当前的节点编号。
- 现在，小 P 想知道，对于这轮游戏，小 Q 会有多少种不同的回答。记这个数量为 $b[i]$，则你需要回答 $b[i]$ 的值。
从标准输入 (stdin) 读入数据。
本题有多组测试数据。
输入的第一行包含一个整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。
第二行包含一个正整数 $T$，表示测试数据组数。
对于每组测试数据：
第一行包含三个正整数 $n,m,k$，以空格分隔。
第二行包含 $n$ 个正整数 $p[1],p[2],p[3],…,p[n]$，以空格分隔。
第三行包含 $m$ 个正整数 $r[1],r[2],r[3],…,r[m]$，以空格分隔。
第四行包含 $m$ 个正整数 $a[1],a[2],a[3],…,a[m]$，以空格分隔。
输出到标准输出 (stdout) 中。
对于每组测试数据：
- 输出一行，包含 $m$ 个整数 $b[1],b[2],b[3],…,b[m]$，以空格分隔。
0 1 5 4 1 1 1 1 3 3 1 1 3 3 2 4 4 5
2 3 2 2
不公開 測資點#0 (4%): 4.8s , <1K
不公開 測資點#1 (4%): 4.8s , <1M
不公開 測資點#2 (4%): 4.8s , <1M
不公開 測資點#3 (4%): 4.8s , <1M
不公開 測資點#4 (4%): 4.8s , <1M
不公開 測資點#5 (4%): 4.8s , <1M
不公開 測資點#6 (4%): 4.8s , <10M
不公開 測資點#7 (4%): 4.8s , <10M
不公開 測資點#8 (4%): 4.8s , <10M
不公開 測資點#9 (4%): 4.8s , <10M
不公開 測資點#10 (4%): 4.8s , <10M
不公開 測資點#11 (4%): 4.8s , <10M
不公開 測資點#12 (4%): 4.8s , <10M
不公開 測資點#13 (4%): 4.8s , <10M
不公開 測資點#14 (4%): 4.8s , <10M
不公開 測資點#15 (4%): 4.8s , <10M
不公開 測資點#16 (4%): 4.8s , <10M
不公開 測資點#17 (4%): 4.8s , <10M
不公開 測資點#18 (4%): 4.8s , <10M
不公開 測資點#19 (4%): 4.8s , <10M
不公開 測資點#20 (4%): 4.8s , <10M
不公開 測資點#21 (4%): 4.8s , <10M
不公開 測資點#22 (4%): 4.8s , <10M
不公開 測資點#23 (4%): 4.8s , <10M
不公開 測資點#24 (4%): 4.8s , <10M
在第一轮游戏中，小 Q 可能会回答的节点有 $2$ 个，编号分别为 $2,3$。
在第二轮游戏中，小 Q 可能会回答的节点有 $3$ 个，编号分别为 $2,4,5$。
在第三轮游戏中，小 Q 可能会回答的节点有 $2$ 个，编号分别为 $4,5$。
在第四轮游戏中，小 Q 可能会回答的节点有 $2$ 个，编号分别为 $4,5$。
定义节点 $i$ 的深度 $d[i]$ 为根节点到节点 $i$ 的简单路径的边数。即 $d[1]=0$，且对于所有满足 $2≤i≤n$ 的整数 $i$，$d[i]=d[p[i]]+1$。定义有根树的高度 $h$ 为所有节点的深度的最大值，即 $h = \max_{i=1}^{n} d[i]$。
数据范围：
- $T≤5$
- $n≤3000$
- $m≤8×10^4$
- $h≤n-1$
- $k≤10^9$
- $p[1]=1$
- 对于所有满足 $2≤i≤n$ 的整数 $i$，$p[i]≤n$。
- 序列 $p$ 所表示的是一棵树。
- 对于所有满足 $1≤i≤m$ 的整数 $i$，$r[i]≤n,a[i]≤n$，且 $a[i]$ 是根节点为 $r[i]$ 的子树中的一个节点。
测试点 $1$ 满足：$n\le 3, m\le 10$。
测试点 $2,3$ 满足：$n\le 150, m\le 400$。
测试点 $4$ 满足：$n\le 500, m\le 10^4$。
测试点 $5,6$ 满足：$n\le 500, m\le 10^4, p[i]\le i-1$。
测试点 $7$ 满足：$p[i]=i-1$。
测试点 $8$~$10$ 满足：$r[1]=r[2]=r[3]=...=r[m]$。
测试点 $11$ 满足：$h=1$。
测试点 $12$ 满足：$h\le 2, r[1]=r[2]=r[3]=...=r[m]$。
测试点 $13,14$ 满足：$h\le 2$。
测试点 $15$ 满足：$k=10^9$。
测试点 $16,17$ 满足：$k=1$。
测试点 $18$~$20$ 满足：$k\le 5$。
测试点 $21,22$ 满足：$p[i]\le i-1$。
测试点 $23$~$25$ 没有额外的约束条件。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||