#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100010
#define inf 1000000000
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll l,r,minz,maxz;
}tr[MAXN*4];
ll n,q,idx=1,cnt;
ll dfn[MAXN],lst[MAXN],val[MAXN],re_dfn[MAXN],dep[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
void push_up(ll now){
	tr[now].maxz=max(tr[now*2].maxz,tr[now*2+1].maxz);
	tr[now].minz=min(tr[now*2].minz,tr[now*2+1].minz);
}	
void build(ll x,ll y){
	nxt[++idx]=hd[x];
	ed[idx]=y;
	hd[x]=idx;
}
void dfs(ll now,ll fa){
	dfn[now]=lst[now]=++cnt;
	dep[now]=dep[fa]+1;
	re_dfn[cnt]=now;
	for(int i=hd[now];i;i=nxt[i]){
		ll y=ed[i];
		if(y==fa)continue;
		dfs(y,now);
		lst[now]=max(lst[now],lst[y]);
	}
}
void build(ll now,ll l,ll r){
	tr[now].l=l,tr[now].r=r;
	tr[now].minz=inf,tr[now].maxz=-inf;
	if(l==r){
		tr[now].minz=tr[now].maxz=val[re_dfn[l]];
		return;
	}
	ll mid=(l+r)/2;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
	push_up(now);
}
void ad_(ll now,ll loc,ll val){
	if(tr[now].l==tr[now].r){
		tr[now].maxz=tr[now].minz=val;
		return;
	}
	ll mid=(tr[now].l+tr[now].r)/2;
	if(loc<=mid)ad_(now*2,loc,val);
	else ad_(now*2+1,loc,val);
	push_up(now);
}
ll re_minz(ll now,ll l,ll r){
	if(tr[now].l>=l&&tr[now].r<=r){
		return tr[now].minz;
	}
	ll mid=(tr[now].l+tr[now].r)/2,ans=inf;
	if(l<=mid)ans=min(ans,re_minz(now*2,l,r));
	if(r>mid)ans=min(ans,re_minz(now*2+1,l,r));
	return ans;
}
ll re_maxz(ll now,ll l,ll r){
	if(tr[now].l>=l&&tr[now].r<=r){
		return tr[now].maxz;
	}
	ll mid=(tr[now].l+tr[now].r)/2,ans=-inf;
	if(l<=mid)ans=max(ans,re_maxz(now*2,l,r));
	if(r>mid)ans=max(ans,re_maxz(now*2+1,l,r));
	return ans;
}
int main(){
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	n=read(),q=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read();
		build(x,y),build(y,x);
	}
	dfs(1,0);
	build(1,1,n);
	for(int i=1;i<=q;i++){
		string type;
		cin>>type;
		if(type=="QUERY"){
			ll id=read();
			ll x=ed[id*2],y=ed[id*2+1];
			if(dep[x]<dep[y])swap(x,y);
			ll min1=inf,min2=inf,max1=-inf,max2=-inf;
			if(dfn[x]>1){
				min1=min(min1,re_minz(1,1,dfn[x]-1));
				max1=max(max1,re_maxz(1,1,dfn[x]-1));
			}
			if(lst[x]<n){
				min1=min(min1,re_minz(1,lst[x]+1,n));
				max1=max(max1,re_maxz(1,lst[x]+1,n));
			}
			min2=re_minz(1,dfn[x],lst[x]);
			max2=re_maxz(1,dfn[x],lst[x]);
			if(min1==inf&&max1==-inf)cout<<min2*max2<<endl;
			else cout<<min2*max2+min1*max1<<endl;
		}else{
			ll loc=read(),val=read();
			ad_(1,dfn[loc],val);
		}
	}
	return 0;
}