轻涟 vaguelette

时间限制 / 3.0s

空间限制 / 1024MB

小 H 在学习轻涟剖分。

对于一棵 $n$ 个结点，边有边权的树 $T$ 和长度为 $m$（$m$ 为偶数），值域在 $[1,n]$ 内的序列 $a$，定义它的贡献 $F(T,a)$ 表示将 $a$ 中元素两两配对后在树上形成的 $\dfrac{m}{2}$ 条路径的长度和的最小值。注意如果有重复元素需要配对多次。

同时，定义它的气氛值 $G(T,a)$ 表示对于 $a$ 的每个长为偶数的子序列 $a'$，$F(T,a')$ 的和。

再定义轻涟值 $H(T,m)$ 表示对于任意合法的，长度为 $m$ 的序列 $p$，$G(T,p)$ 的和。

小 H 使用轻涟剖分轻松的解决了这个问题，于是小 Y 决定加强一下。

问题一：给定 $n$ 个结点的树 $T$ 和偶数 $m$，请对其中的所有连通块 $T'$，求 $H(T',m)$ 的和。

小 H 再次使用轻涟剖分轻松的解决了这个问题。但这次跟上次不同的是，小 Y 抽干了小 H 的龙脉，小 H 失忆了。

在失忆之后，小 H 想要回忆起问题的答案，却发现自己只记得前 $k$ 个点跟它父亲之间的边权，却忘记了所有点的父亲。不过他还知道一件事情，那就是 每个非根结点的父亲编号都小于它自身的编号。

问题二：小 H 想知道，在仅保留前 $k$ 个点的情况下，所有合法的树中，问题一的答案之和。

答案对 $10^9+7$ 取模。

第一行，输入 $n,m,k$。

接下来一行，输入 $n-1$ 个数，表示 $fa_{2\cdots n}$。

接下来一行，输入 $n-1$ 个数，表示 $val_{2\cdots n}$，也就是每个点与它的父亲之间的边权。

输出一行两个数分别表示两问的答案。

第一问正确会获得 60% 的分数，第二问正确会获得 40% 的分数。如果你不会某一问，请随便输出一个数以保证格式正确。每个子任务的评分取该子任务中每个测试点的得分最小值。

4 4 4
1 2 3
1 2 1

4944 28976

7 7 7
1 1 2 2 3 3
5 4 3 2 1 2

42528697 1655828

该题还附加了 15 个额外样例，分别对应每个子任务的限制情况。

对于 100% 的数据，$1\le n\le 7.5\times 10^3$，$2\le m\le 10^9$，$1\le k\le 500$，$1\le fa_i

保证除前两个样例外，均有 $1\le k\le \lceil \dfrac{n}{15}\rceil$。

子任务编号	分值	$n\le$	$m\le$	特殊性质
1	10	$4$	$2$	无
2	5	$20$	$20$	无
3	5	$50$	$50$	无
4	5	$100$	$100$	无
5	5	$200$	$200$	无
6	5	$300$	$300$	无
7	5	$5\times 10^3$	$10^9$	$fa_i=i-1$
8	10	$5\times 10^3$	$10^9$	$val_i=1$
9	5	$5\times 10^3$	$2$	无
10	5	$1.25\times 10^3$	$10^9$	无
11	10	$2.5\times 10^3$	$10^9$	无
12	5	$3.75\times 10^3$	$10^9$	无
13	10	$5\times 10^3$	$10^9$	无
14	5	$6.25\times 10^3$	$10^9$	无
15	10	$7.5\times 10^3$	$10^9$	无

在样例一的问题一中，连通块 1-2，2-3，3-4 造成的贡献分别为 56，112，56；连通块 1-2-3，2-3-4 造成的贡献均为 768；连通块 1-2-3-4 造成的贡献为 3184。

在样例一的问题二中，可以列出如下表格：

邂逅编程之美