F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4154. -- [Ipsc2015]Generating Synergy

4154: [Ipsc2015]Generating Synergy

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 1065  Solved: 405
[Submit][Status][Discuss]

Description

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色

Input

第一行一个数T,表示数据组数
接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数
接下来一行n-1个数描述2..n的父节点
接下来q行每行三个数a,l,c
若c为0,表示询问a的颜色
否则将距离a不超过l的a的子节点染成c

Output

设当前是第i个操作,y_i为本次询问的答案(若本次操作是一个修改则y_i为0),令z_i=i*y_i,请输出z_1+z_2+...+z_q模10^9+7

Sample Input

1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0

Sample Output

32

HINT



第1,3,5,7的询问的答案分别为1,3,3,1,所以答案为 1*1+2*0+3*3+4*0+5*3+6*0+7*1=32.

数据范围:

对于100%的数据T<=6,n,m,c<=10^5,

1<=a<=n,0<=l<=n,0<=c<=c




Source

[Submit][Status][Discuss]

HOME Back