初赛第一场（4月19）：题目2：树

题目2 : 树

时间限制:4000ms

单点时限:2000ms

内存限制:256MB

描述

有一个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 ≤ 10⁵)，表示树的节点总数。

接下来N - 1行，每行1个数，a (1 ≤ a ≤ N)，依次表示2..N节点的父亲节点的编号。

接下来一个整数Q(1 ≤ Q ≤ 10⁵)，表示操作总数。

接下来Q行，每行4个整数，u, l, r, delta (1 ≤ u ≤ N, 1 ≤ l ≤ r ≤ N, -10⁹ ≤ delta ≤ 10⁹)，代表一次操作。

输出

对每组数据，先输出一行“Case x: ”，x表示是第几组数据，然后接这组数据答案的Hash值。

数据范围

小数据：1 ≤ N, Q ≤ 1000

大数据：1 ≤ N, Q ≤ 10⁵

样例解释

点1的子树中有1,2,3三个节点。其中深度在2-3之间的是点2和点3。

点2的子树中有2,3两个节点。其中没有深度为1的节点。

所以，执行完所有操作之后，只有2,3两点的权值增加了1。即答案是0 1 1。再计算对应的Hash值即可。

样例输入

样例输出

Case 1: 12348

解析：要注意可以是任意树。操作后深度会不发生改变。可以用（mulitmap ）关联数组来表示关系。

代码：

 1 #include <iostream>
 2 #include <string>
 3 #include <map>
 4 #include <queue>
 5 using namespace std;
 6 const int MOD = 1e+9 +7;
 7 unsigned long long magic = 12347;
 8 unsigned answer[100001];
 9 unsigned depth[100001];
10 
11 void update_answer(int u, int l, int r, int delta)
12 {
13     if(depth[u] >= l && depth[u] <= r) 
14     {
15         answer[u] += delta; 
16     }
17 }
18 
19 void bfs(int u, multimap<int, int>& mm, int l, int r, int delta)
20 {
21     queue<int> qu;
22     qu.push(u);
23     while(!qu.empty())
24     {
25         int v = qu.front();
26         pair<multimap<int, int>::iterator, multimap<int, int>::iterator> re = mm.equal_range(v);
27         qu.pop();
28         for(multimap<int, int>::iterator it = re.first; it != re.second; ++it)
29             qu.push((*it).second);
30         update_answer(v, l, r, delta);
31     }
32 }
33 
34 int main()
35 {
36     int T;
37     cin >>T;
38     for(int k = 0; k <= T; ++k)
39     {
40         int N;
41         cin >> N;
42         memset(answer, 0, sizeof(answer));
43         memset(depth, 0, sizeof(depth));
44         depth[1] = 1;
45         multimap<int,int> mm;
46         for(int i = 2; i <= N; ++i)
47         {
48             int father;
49             scanf("%d",&father);
50             mm.insert(make_pair(father, i));
51             depth[i] = depth[father] + 1;
52         }
53         int Q;
54         int u, l, r, delta;
55         cin >> Q;
56         while(Q--)
57         {
58             cin >> u >> l >> r >> delta;
59             bfs(u, mm, l, r, delta);
60         }
61         unsigned long long  hash = 0;
62         for(int i = 1; i <= N; ++i)
63         {
64             hash = (hash * magic + answer[i]) % MOD;
65         }
66         cout << "Case " << k+1 << ": " << hash << endl;
67     }
68     return 0;
69 }