#P10100. [2024省队模拟]轻涟

    ID: 9155 传统题 5000ms 888MiB 尝试: 10 已通过: 1 难度: 10 上传者: 标签>组合数学树算法树链剖分LCACF3100树形DP计数DP多项式线段树

[2024省队模拟]轻涟

轻涟(vaguelette)

【题目描述】

小青蛙在学习轻涟剖分。

对于一棵nn个节点、边有边权的树TT,以及偶数长度为 ss、元素位于节点集内的序列aa,定义贡献 F(T,a)F(T,a) 为将 aa 中元素两两配对后,在树上形成的 s/2s/2 条路径的长度和的最小值。重复元素需要按出现次数参与配对。

同时,定义它的轻呱值G(T,a)G(T,a) 表示对于aa 的每个长为偶数的子序列a′a^{′},F(T,a′)F(T,a^{′}) 的和。

再定义轻涟值H(T,m)H(T,m) 表示对于任意合法的,长度为mm的序列pp,G(T,p)G(T,p) 的和。 小青蛙使用轻涟剖分轻松的解决了这个问题,于是他的好朋友小青呱决定加强一下。 问题一:给定 nn 个节点的树 TT 和整数 mm,请对于其中的所有连通块T′T^{′},求 H(T′,m)H(T^{′},m) 的和。

小青蛙再次使用轻涟剖分轻松的解决了这个问题。但这之后小青蛙便忙着去玩卡牌游戏了,等到回来之后发现自己只记得前kk 个点跟它们父亲之间的边权,忘记了这些点的父亲。不过他还记得一件事情,那就是每个非根结点的父亲编号都小于它自身的编号。 问题二:小青蛙想知道,在仅保留前kk 个点的情况下,所有合法的树中,问题一的答案之和。

小青蛙的脑容量不算很大(从他健忘就可以看出来),所以你只需要求出这两问的答案对 109+710^{9}+7取模的值。

【输入格式】

从标准输入读入。

第一行三个整数n,m,kn,m,k,意义如题面所示。

第二行n−1n-1 个整数,其中第ii 个数 fai+1fa_{i+1} 表示i+1i+1的父亲。

第三行n−1n-1 个整数,其中第ii个数 vali+1val_{i+1} 表示i+1i+1 的与它父亲之间的边权。

【输出格式】

输出到标准输出。

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

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

【样例 1 输入】

4 4 4
1 2 3
1 2 1

【样例 1 输出】

4944 28976

【样例 2 输入】

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

【样例 2 输出】

42528697 1655828

【样例 3∼173\sim17】

见选手目录下的 vaguelette/vaguelette3 ∼ 17.in 与 vaguelette/vaguelette3 ∼ 17.ans。

对于i∈[1,15]i\in [1,15],第i+2i+2 个样例满足子任务ii的限制。

【数据范围】

对于 100100% 的数据,$1\le n\le 7500,2\le m\le 10^{9},1\le k\le\min(n,500),1\le fa_{i}<i,1\le$ vali≤109val_{i}\le 10^{9}。

序列总长度 mm 可以是奇数;GG 始终只统计偶数长度的子序列,FF 也仅作用于这些偶数长度子序列。

第二问仅保留编号 1,2,…,k1,2,\ldots,k 的节点,保证 k≤nk\le n。

子任务编号 n≤n\le m≤m\le 特殊性质 子任务分值
1 4 2 1010
2 2020 20 55
33 5050
44 100100
55 200200
66 300300
7 5000 10910^{9} fai=i−1fa_{i}=i-1 5
88 fai=1fa_{i}=1 1010
99 22 5
1010 1250 10910^{9}
1111 2500 1010
1212 3750 5
1313 5000 1010
1414 6250 5
1515 7500 1010