#P10100. [2024省队模拟]轻涟
[2024省队模拟]轻涟
轻涟(vaguelette)
【题目描述】
小青蛙在学习轻涟剖分。
对于一棵个节点、边有边权的树,以及偶数长度为 、元素位于节点集内的序列,定义贡献 为将 中元素两两配对后,在树上形成的 条路径的长度和的最小值。重复元素需要按出现次数参与配对。
同时,定义它的轻呱值 表示对于 的每个长为偶数的子序列, 的和。
再定义轻涟值 表示对于任意合法的,长度为的序列, 的和。 小青蛙使用轻涟剖分轻松的解决了这个问题,于是他的好朋友小青呱决定加强一下。 问题一:给定 个节点的树 和整数 ,请对于其中的所有连通块,求 的和。
小青蛙再次使用轻涟剖分轻松的解决了这个问题。但这之后小青蛙便忙着去玩卡牌游戏了,等到回来之后发现自己只记得前 个点跟它们父亲之间的边权,忘记了这些点的父亲。不过他还记得一件事情,那就是每个非根结点的父亲编号都小于它自身的编号。 问题二:小青蛙想知道,在仅保留前 个点的情况下,所有合法的树中,问题一的答案之和。
小青蛙的脑容量不算很大(从他健忘就可以看出来),所以你只需要求出这两问的答案对 取模的值。
【输入格式】
从标准输入读入。
第一行三个整数,意义如题面所示。
第二行 个整数,其中第 个数 表示的父亲。
第三行 个整数,其中第个数 表示 的与它父亲之间的边权。
【输出格式】
输出到标准输出。
一行两个数,分别表示两问的答案。
第一问正确会获得 % 的分数,第二问正确会获得 % 的分数。如果你不会某一问,请随便输出一个数以保证格式正确。每个子任务的评分取该子任务中每个测试点的得分最小值。
【样例 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
【样例 】
见选手目录下的 vaguelette/vaguelette3 ∼ 17.in 与 vaguelette/vaguelette3 ∼ 17.ans。
对于,第 个样例满足子任务的限制。
【数据范围】
对于 % 的数据,$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$ 。
序列总长度 可以是奇数; 始终只统计偶数长度的子序列, 也仅作用于这些偶数长度子序列。
第二问仅保留编号 的节点,保证 。
| 子任务编号 | 特殊性质 | 子任务分值 | ||
|---|---|---|---|---|
| 1 | 4 | 2 | ||
| 2 | 20 | |||
| 7 | 5000 | 5 | ||
| 5 | ||||
| 1250 | ||||
| 2500 | ||||
| 3750 | 5 | |||
| 5000 | ||||
| 6250 | 5 | |||
| 7500 | ||||