记录编号	321438	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.356 s
提交时间	2016-10-13 19:04:20	内存使用	10.44 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;namespace mine{
	template<class T>inline void readint(T &__x){
		static int __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)__x=-__x;
	}
	template<class T>inline void putint(T __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%(T)10^(T)48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=140010;//131072
struct edge{int to,prev;}e[maxn<<1];
void addedge(int,int);
void dfs(int);
void mset(int,LL);
LL qmin(int,int);
LL qmax(int,int);
LL w[maxn],mn[maxn<<1],mx[maxn<<1],d;
int n,M=1,m,last[maxn],len=0,prt[maxn],low[maxn],dfn[maxn],finish[maxn],tim=0,x,y;
char c[20];
int main(){
#define MINE
#ifdef MINE
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
#endif
	readint(n);
	readint(m);
	while(M<n+2)M<<=1;
	for(int i=1;i<=n;i++)readint(w[i]);
	for(int i=1;i<n;i++){
		readint(x);
		readint(y);
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1);
	for(int i=n+M+1;i<(M<<1);i++)mn[i]=~(1ll<<63);
	for(int i=M-1;i;i--){
		mn[i]=min(mn[i<<1],mn[i<<1|1]);
		mx[i]=max(mx[i<<1],mx[i<<1|1]);
	}
	while(m--){
		scanf("%s",c);
		readint(x);
		if(*c=='Q'){
			x=low[x];
			putint(min(qmin(1,dfn[x]-1),qmin(finish[x]+1,n))*max(qmax(1,dfn[x]-1),qmax(finish[x]+1,n))+qmin(dfn[x],finish[x])*qmax(dfn[x],finish[x]));
			putchar('\n');
		}
		else{
			readint(d);
			mset(dfn[x],d);
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y){
	e[++len].to=y;
	e[len].prev=last[x];
	last[x]=len;
}
void dfs(int x){
	dfn[x]=++tim;
	mn[tim+M]=mx[tim+M]=w[x];
	for(int i=last[x];i;i=e[i].prev)if(e[i].to!=prt[x]){
		prt[e[i].to]=x;
		low[(i+1)>>1]=e[i].to;
		dfs(e[i].to);
	}
	finish[x]=tim;
}
void mset(int x,LL d){
	x+=M;
	mn[x]=mx[x]=d;
	for(x>>=1;x;x>>=1){
		mn[x]=min(mn[x<<1],mn[x<<1|1]);
		mx[x]=max(mx[x<<1],mx[x<<1|1]);
	}
}
LL qmin(int l,int r){
	if(l>r)return ~(1ll<<63);
	LL ans=~(1ll<<63);
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=min(ans,mn[l^1]);
		if(r&1)ans=min(ans,mn[r^1]);
	}
	return ans;
}
LL qmax(int l,int r){
	if(l>r)return 1ll<<63;
	LL ans=1ll<<63;
	for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=max(ans,mx[l^1]);
		if(r&1)ans=max(ans,mx[r^1]);
	}
	return ans;
}
/*
5 10000
10 2 5 3 7
1 2
2 4
5 4
2 3
*/