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

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;
}