编程之美初赛第一场--树

我会带着你远行 2022-08-26 15:19 192阅读 0赞

### 题目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 ≤ 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值即可。

样例输入

1
    3
    1
    2
    2
    1 2 3 1
    2 1 1 1

样例输出

Case 1: 12348

解析：开始没看这道题，以为这道题是什么树或者图的算法，虽然前一段时间写了关于表达式树，红黑树什么的，但是一看那题那么长，还有权重，这难道是什么图搜索还是。。。水货还没练过搜索的题，唉……最后看了看第三题--活动中心，题意挺简单，但是没思路哈，也怪自己平时做的题实在的太少了，扯的优点多，后来剩下了不到半小时的时间去仔细的看了下这道题，大致题意思：给出了树的节点个数以及每个节点的父亲节点，其中定义根节点的深度为1，其他节点的深度依次根据根节点来定义，然后输入了几组操作的命令，其实就是让你找给定u的所有子节点，并判断他们的深度是否在l和r之间，如果在的话则对应节点的权重+delta，最后按照题目指定的题意输出就好了，题意大致如此，很明显需要定义权重的数组，节点编号的数组，记录每个节点父节点的数组。

最后慌慌张张写好了，结果时间也过了没办法提交验证自己是不是对，大数据肯定是过不了，唉……竟然好多大神那么短的时间内全部做完并且数据全过哈！膜拜大神哈！

#include <iostream>
    #include <stdio.h>
    #include <memory.h>
    using std::endl;
    using std::cin;
    using std::cout;
    int main()
    {
    	int Parent[1001];
    	int Depth[1001];
    	int Answer[1001];
    	int T;
    	cin >> T;
    	int cnt=0;
    	while(T--)
    	{
    		cnt++;
    		//初始化
    		memset(Parent,0,sizeof(Parent));
    		memset(Depth,0,sizeof(Depth));
    		memset(Answer,0,sizeof(Answer));
    		//初始化根节点编号的深度值
    		Depth[1]=1;
    		int N;
    		cin >> N;
    		int n;
    		//输入2..N节点的父亲节点的编号
    		for(int i=2;i<=N;++i)
    		{
    			cin >> n;
    			//存储父亲节点
    			Parent[i]=n;
    			//更新深度
    			Depth[i]=Depth[n]+1;
    		}
    		int Q;
    		//输入操作的次数
    		cin >> Q;
    		int u, l, r, delta;
    		for(int i=0;i<Q;++i)
    		{
    			cin >> u >> l >> r >> delta;
    			for(int j=1;j<=N;++j)
    			{
    				//u的子树包括u节点本身
    				if(Depth[u]>=l&&Depth[u]<=r)
    				{
    					Answer[u]+=delta;
    				}
    				//如果节点的深度小于或者等于u，则不可能是u(除了u本身外)的子树
    				if(Depth[j]>Depth[u])
    				{
    					if(Parent[j]==u)
    					{//u的第一代孩子
    						if(Depth[j]>=l&&Depth[j]<=r)
    						{
    							Answer[j]+=delta;
    						}
    					}else{
    						//不是u的直接孩子
    						int temp=j;
    						while(Depth[temp]!=Depth[u])
    						{
    							temp=Parent[temp];
    						}
    						//来判断是否为u的子树节点
    						if(temp==u&&(Depth[j]>=l&&Depth[j]<=r))
    						{
    							Answer[j]+=delta;
    						}
    					}
    				}
    			}
    		}
    		//对存储在Answer中的权值进行最后的输出处理
    		int MOD =1000000007; // 10^9 + 7
    		int MAGIC= 12347;
    		int Hash =0;
    		for(int i=1;i<=N;++i)
    		{
    			Hash = (Hash * MAGIC + Answer[i]) % MOD;
    		}
    		//输出
    		cout << "Case " << cnt << ": ";
    		cout << Hash << endl;
    	}
    	return 0;
    }

Emacs Normal Vim