接下来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值就可以。
例子输入
1
3
1
2
2
1 2 3 1
2 1 1 1
例子输出
Case 1: 12348
以下的c++代码尽管通过測试例子,可是WR了。有知道问题出在哪里的,恳请指出来~
#include <iostream>
#include <cstdio>
#include <cstdlib>
int depth_n;
long mode = 1000000000+7;
int magic = 12347;
int find_parent(int n, int *parent, int depth)
if (n == parent[n])
depth_n = depth;
return n;
else return find_parent(parent[n], parent, depth+1);
int main()
int T,t;
scanf("%d", &T);
for(t = 1; t <= T; t++)
int N, i;
scanf("%d", &N);
int *parent = new int[N+1];
long long *ans = new long long[N+1];
for (i = 0; i < N+1; i++)
ans[i] = 0;
parent[1] = 1;
for (i = 2; i <= N; i++)
scanf("%d", &parent[i]);
int Q, u, l, r;
long long delta;
scanf("%d", &Q);
for ( i = 0; i < Q; i++)
scanf("%d %d %d %lld", &u, &l, &r, &delta);
if (u > N || u < 1)
continue;
if (l > r || r > N || l < 1)
continue;
int n;
for ( n = 1; n <= N; n++)
depth_n = 1;
if (find_parent(n, parent, depth_n) == u)
if (r >= depth_n && l <= depth_n)
ans[n] += delta;
long long hash_n = 0;
for ( i = 1; i <= N; i++)
hash_n = (hash_n*magic + ans[i])%mode;
printf("Case %d: %lld\n",t, hash_n);
delete[] ans;
delete[] parent;
system("pause");
return 0;