记录编号	255421	评测结果	AAAAAATTTT
题目名称	2288.[HZOI 2015]疯狂的魔法树	最终得分	60
用户昵称	Aglove	是否通过	未通过
代码语言	C++	运行时间	9.103 s
提交时间	2016-04-27 19:03:51	内存使用	5.66 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;

const int maxn=200010;
int n,m,u,v,a,b,val;
int h[maxn],cnt=0;
int c[maxn];
struct edge{
	int to,next;
}G[maxn<<1];
int fa[maxn],ans=0;
void add(int x,int y){
	++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;
}
void DFS(int u,int f){
	fa[u]=f;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==f)continue;
		DFS(v,u);
	}return;
}
void Get_ans(int u){
	if(c[u]>=a&&c[u]<=b)ans++;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==fa[u])continue;
		Get_ans(v);
	}return;
}
void Get_add(int u){
	c[u]+=val;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==fa[u])continue;
		Get_add(v);
	}return;
}
void Get_modify(int u){
	c[u]=val;
	for(int i=h[u];i;i=G[i].next){
		int v=G[i].to;
		if(v==fa[u])continue;
		Get_modify(v);
	}return;
}
void debug(){
	for(int i=1;i<=n;++i)printf("%d ",c[i]);
	printf("\n");return;
}
int main(){
	freopen("H_Tree.in","r",stdin);
	freopen("H_Tree.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&c[i]);
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}DFS(1,-1);
	for(int i=1;i<=m;++i){
		char ch=getchar();
		while(ch<'!')ch=getchar();
		if(ch=='Q'){
			scanf("%d%d%d",&u,&a,&b);
			ans=0;Get_ans(u);
			printf("%d\n",ans);
		}else if(ch=='M'){
			scanf("%d%d",&u,&val);
			c[u]=val;
		}else if(ch=='C'){
			scanf("%d%d",&u,&val);
			Get_add(u);
		}else if(ch=='W'){
			scanf("%d%d",&u,&val);
			Get_modify(u);
		}else{
			scanf("%d%d",&u,&v);
			n++;fa[n]=u;add(u,n);
			c[n]=v;
		}
		//debug();
	}return 0;
}