大家好,又见面了,我是全栈君。
题目2 : 树
4000ms
2000ms
256MB
- 例子输入
-
1 3 1 2 2 1 2 3 1 2 1 1 1
- 例子输出
-
Case 1: 12348
描写叙述
有一个N个节点的树。当中点1是根。初始点权值都是0。
一个节点的深度定义为其父节点的深度+1,。特别的。根节点的深度定义为1。
如今须要支持一系列下面操作:给节点u的子树中,深度在l和r之间的节点的权值(这里的深度依旧从整个树的根节点開始计算)。都加上一个数delta。
问完毕全部操作后,各节点的权值是多少。
为了降低巨大输出带来的开销。如果完毕全部操作后。各节点的权值是answer[1..N],请你依照例如以下方式计算出一个Hash值(请选择合适的数据类型。注意避免溢出的情况)。终于仅仅须要输出这个Hash值就可以。
MOD =1000000007; // 10^9 + 7
MAGIC= 12347;
Hash =0;
For i= 1 to N do
Hash = (Hash * MAGIC + answer[i]) mod MOD;
EndFor
输入
第一行一个整数T (1 ≤ T ≤ 5)。表示数据组数。
接下来是T组输入数据。測试数据之间没有空行。
每组数据格式例如以下:
第一行一个整数N (1 ≤ N ≤ 105)。表示树的节点总数。
接下来N – 1行,每行1个数。a (1 ≤ a ≤ N),依次表示2..N节点的父亲节点的编号。
接下来一个整数Q(1 ≤ Q ≤ 105),表示操作总数。
接下来Q行,每行4个整数。u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -109 ≤ delta ≤ 109),代表一次操作。
输出
对每组数据。先输出一行“Case x: ”,x表示是第几组数据,然后接这组数据答案的Hash值。
数据范围
小数据:1 ≤ N, Q ≤ 1000
大数据:1 ≤ N, Q ≤ 105
例子解释
点1的子树中有1,2,3三个节点。当中深度在2-3之间的是点2和点3。
点2的子树中有2,3两个节点。当中没有深度为1的节点。
所以,运行全然部操作之后,仅仅有2,3两点的权值添加了1。即答案是0 1 1。再计算相应的Hash值就可以。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115562.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...