#P14564. 和求

    ID: 13781 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300树形DP背包DP模运算数学多项式动态规划

和求

题目描述

给出一棵 nn 个节点的树,每个点有点权 ava_v。定义一棵树的一个子连通块为一个树中点的非空集合,满足这些点在树上形成一个连通块。定义子连通块 SS 的权值为 ∏v∈S(av+∣S∣)\prod_{v\in S}(a_v+|S|)。求所有子连通块的权值之和对 UVU^V 取模。

如果你认为自己做法的复杂度正确而被卡常,请尝试减少取模次数或优化无用转移。

输入格式

第一行,三个正整数 n,U,Vn,U,V,分别表示节点个数,以及模数(UVU^V)。

第二行,n−1n-1 个正整数 f2,f3,…,fnf_2,f_3,\dots,f_n,分别表示以 11 节点为根节点的情况下第 ii 个点的父亲节点。

第三行,nn 个非负整数 aia_i,表示每个点的点权。

输出格式

一行,一个正整数,表示所有子联通块的权值之和,对 UVU^V 取模。

样例输入 1

3 10 6
1 1
1 2 3

样例输出 1

156

样例解释 1

对于样例 11,以下子连通块的权值分别是:

  • {1}\{1\}:(1+1)=2(1+1)=2;
  • {2}\{2\}:(2+1)=3(2+1)=3;
  • {3}\{3\}:(3+1)=4(3+1)=4;
  • {1,2}\{1,2\}:(1+2)×(2+2)=12(1+2)\times(2+2)=12;
  • {1,3}\{1,3\}:(1+2)×(3+2)=15(1+2)\times(3+2)=15;
  • {1,2,3}\{1,2,3\}:(1+3)×(2+3)×(3+3)=120(1+3)\times(2+3)\times(3+3)=120。

总和为 2+3+4+12+15+120=1562+3+4+12+15+120=156,对 10610^6 取模后为 156156。

样例输入 2

11 4 6
1 1 2 3 4 4 4 5 6 7
325 190 400 325 380 165 334 400 80 171 340

样例输出 2

678

样例 3~9

见附加文件。分别满足每个子任务的限制。

数据范围

对于所有数据满足 1≤n≤20001\leq n\leq2000,1≤fi<i1\leq f_i<i,2≤U≤102\leq U\leq10,1≤V≤61\leq V\leq6,0≤ai≤1060\leq a_i\le 10^6。

子任务编号 特殊性质 分值
11 n≤10n\leq10 44
22 n≤150n\leq150 88
33 n≤500n\leq500 1212
44 U=2,V=1U=2,V=1 88
55 V=1V=1 2424
66 U∣aiU\mid a_i
77 无特殊限制 2020