记录编号	98912	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	GDFRWMY	是否通过	通过
代码语言	C++	运行时间	0.927 s
提交时间	2014-04-25 15:32:50	内存使用	61.35 MiB

#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("westward.in");
ofstream fout("westward.out");
const long long INF=1e17;
int ll[1000000],rr[1000000],lc[1000000],rc[1000000];
long long minw[1000000],maxw[1000000];
int dfn[1000000],qwe[1000000],pos[1000000],deep[1000000];
int edges[1000000],edgex[1000000];
int n,q,tot,tol,w[500000],u,v;
vector<int> c[500000];
void build(int root,int l,int r){
    ll[root]=l;
	rr[root]=r;
	if (l<r){
		tot++;
		lc[root]=tot;
		build(tot,l,(l+r)/2);
		tot++;
		rc[root]=tot;
		build(tot,(l+r)/2+1,r);
		if (lc[root]!=-1){
			if (minw[lc[root]]>minw[rc[root]])
			minw[root]=minw[rc[root]]; else minw[root]=minw[lc[root]]; 
		if (maxw[lc[root]]>maxw[rc[root]])
			maxw[root]=maxw[lc[root]]; else maxw[root]=maxw[rc[root]]; 
		//fout<<minw[lc[root]]<<' '<<minw[rc[root]]<<endl;
		}
	}
	else
	{lc[root]=-1;
	rc[root]=-1;
	minw[root]=maxw[root]=w[qwe[l]];
	//fout<<maxw[root]<<endl;
	}
	
	
}
void change(int root,int x,long long p){
	
	if (root==-1) return;
		//fout<<ll[root]<<' '<<rr[root]<<x<<p<<endl;
	if (ll[root]>x||rr[root]<x) return;

	if (ll[root]==x&&rr[root]==x){
		minw[root]=p;
		maxw[root]=p;
		//fout<<ll[root]<<' '<<rr[root]<<p<<endl;
		//fout<<x<<endl;
	}
	else{
		change(lc[root],x,p);
		change(rc[root],x,p);
		
		if (lc[root]!=-1){
			//fout<<minw[lc[root]]<<' '<<minw[rc[root]]<<endl;
		if (minw[lc[root]]>minw[rc[root]])
			minw[root]=minw[rc[root]]; else minw[root]=minw[lc[root]]; 
		if (maxw[lc[root]]>maxw[rc[root]])
			maxw[root]=maxw[lc[root]]; else maxw[root]=maxw[rc[root]]; 
		}
	}
	//fout<<maxw[root]<<endl;
	
}

pair<long long,long long> gets (int root,int x,int y){
	if(root==-1) return make_pair(0,INF);
	//fout<<ll[root]<<' '<<rr[root]<<endl;
	if(ll[root]>y||rr[root]<x) return make_pair(0,INF);
    if(ll[root]>=x&&rr[root]<=y) return make_pair(maxw[root],minw[root]);

 pair <long long,long long> x1,x2;
	x1=gets(lc[root],x,y);
x2=gets(rc[root],x,y);
	//fout<<x1.first<<' '<<x2.first<<' ';
	//fout<<x1.second<<' '<<x2.second<<endl;
	//fout<<x1.second<<' '<<x2.second<<endl;

return make_pair(max(x1.first,x2.first),min(x1.second,x2.second));
}
long long query(int x){
int	u=edges[x],v=edgex[x];

pair <long long,long long>  w1,t1,t2,w2;
w1=gets(1,dfn[v],dfn[v]+pos[v]-1);
t1=gets(1,1,dfn[v]-1);
t2=gets(1,dfn[v]+pos[v],n);
w2=make_pair(max(t1.first,t2.first),min(t1.second,t2.second));
//fout<<dfn[v]<<' ' <<pos[v]-1<<endl;
//fout<<w1.first<<' '<<w1.second<<' '<<w2.first<<' '<<w2.second<<endl;
return w1.first*w1.second+w2.first*w2.second;
}
	
void dfs(int x,int fa){
	tol++;
	dfn[x]=tol;
	qwe[tol]=x;
	//fout<<qwe[tol]<<endl;
	for(int i=0;i<c[x].size();i++)
		if(c[x][i]!=fa){
			deep[c[x][i]]=deep[x]+1;
			dfs(c[x][i],x);
			pos[x]+=pos[c[x][i]];
			//fout<<deep[c[x][i]]<<endl;
		}
		pos[x]++;
}
int main(){
	fin>>n>>q;
	for(int i=1;i<=n;i++)
		fin>>w[i];
	for(int i=1;i<n;i++){
		fin>>u>>v;
		edges[i]=u;
		edgex[i]=v;
		c[u].push_back(v);
		c[v].push_back(u);
	}
	dfs(1,0);
	
	tot=1;
	build(1,1,n);
	int z;
	for(int i=1;i<n;i++)
		if (deep[edges[i]]>deep[edgex[i]]){
			z=edges[i];
			edges[i]=edgex[i];
			edgex[i]=z;
		}
			
	for(int i=1;i<=q;i++){
		string s;
		int x;
		long long r;
			fin>>s;
            if(s[0]=='C'){
			   fin>>x>>r;
               change(1,dfn[x],r);
            }
            else if(s[0]=='Q'){
                    fin>>x;
                    fout<<query(x)<<endl;
                 }
    }
	return 0;
}