首页 > 试题广场 >

白云的树

[编程题]白云的树
白云有一棵n个结点的树，以1号结点为根，这棵树的每个结点有一个权值vali。
定义一个连通块的喜爱度为块内所有结点权值的乘积。
白兔有很多疑问，每个疑问有两个参数k,s，表示询问所有经过点k的大小为s的连通块的喜爱度之和。
白云会定期对树做一些修改。

输入描述:
第一行1个整数n,Q，表示树的结点个数和事件个数。
第二行n个整数表示val1 ... n。
第三行n-1个整数表示2...n号结点的父亲。
接下来Q行，第一个数为op∈{0,1}，
如果op=0表示白云要对某个结点的权值进行修改，接下来两个数k,c表示把结点k的权值修改为c。
如果op=1表示白兔的疑问，接下来两个数k,s。



输出描述:
 对于op=1，每行一个数表示答案。答案对109+7取模。
示例1

输入

15 15
6 4 8 6 8 9 10 9 2 9 8 3 3 6 2
1 1 1 3 1 3 6 5 3 10 9 7 9 13
1 13 8
1 2 4
1 12 8
1 11 2
0 2 9
0 11 4
1 3 6
0 4 5
1 13 7
1 8 2
1 7 6
1 7 8
0 5 5
0 1 7
1 1 6

输出

128592000
11304
35520768
72
10402608
16325280
81
6030720
359079840
8686888

备注:
结点k的父亲为1...k-1的一个均匀随机整数。
vali∈[1,109+7),s≤10,n,Q≤10^5
算法知识视频讲解
开通博客

暂无题解

问题信息

动态规划 树
上传者：牛客301599号
难度：
0条回答 14浏览

热门推荐

通过挑战的用户

查看代码

相关试题

白云的树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号