记录编号	437134	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.796 s
提交时间	2017-08-13 17:47:42	内存使用	7.56 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define ll long long 
using namespace std;
/*
	树剖，修改直接改
	查询的话，查询两个部分最值，再计算答案（答案开long long）
	查询破坏的是路。(路要存)
	分成两个部分，1--e[j]浅点，e[j].深点--n;
	以上查询是错的，
	因为是树不是链，有可能被分裂出的两个块其中一个只是一个点；
	所以不分重链进行剖分，直接维护dfs序
	子树节点在dfs序中是紧挨的
	记录一个节点dfs序，同时记录该节点子树最后一个在dfs序中的位置；
	所以查询就是1到id(深点)-1；en(深点)+1到n
	和id(深点)到en(深点)三块；
	注意别越界。 
*/
inline int read(){
	int 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<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=100010;
int n,m;
vector <int> t[maxn];
struct ee{int u,v;}e[maxn];
int val[maxn],fa[maxn],id[maxn],pre[maxn],tot;
int maxx[4*maxn],minn[4*maxn];
int en[maxn],dep[maxn];
inline void dfs(int u,int f,int d){
	id[u]=en[u]=++tot;pre[tot]=u;fa[u]=f;dep[u]=d;
	for(int i=0;i<t[u].size();i++){
		int v=t[u][i];
		if(v==f)continue;
		dfs(v,u,d+1);
		en[u]=max(en[u],en[v]);
	}
}
inline void build(int o,int l,int r){
	if(l==r){
		maxx[o]=minn[o]=val[pre[l]];
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	build(ls,l,m);
	build(rs,m+1,r);
	maxx[o]=max(maxx[ls],maxx[rs]);
	minn[o]=min(minn[ls],minn[rs]);
}
inline void change(int o,int l,int r,int nl,int nr,int v){
	if(l>=nl&&r<=nr){
		maxx[o]=minn[o]=v;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)change(ls,l,m,nl,nr,v);
	if(m<nr)change(rs,m+1,r,nl,nr,v);
	maxx[o]=max(maxx[ls],maxx[rs]);
	minn[o]=min(minn[ls],minn[rs]);
}
inline int findmax(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		return maxx[o];
	}
	int ans=-0x7fffffff;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)ans=max(ans,findmax(ls,l,m,nl,nr));
	if(m<nr)ans=max(ans,findmax(rs,m+1,r,nl,nr));
	return ans;
}
inline int findmin(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		return minn[o];
	}
	int ans=0x7fffffff;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)ans=min(ans,findmin(ls,l,m,nl,nr));
	if(m<nr)ans=min(ans,findmin(rs,m+1,r,nl,nr));
	return ans;
}
inline ll getans(int p){
	int u=e[p].u,v=e[p].v;
	if(dep[u]>dep[v])swap(u,v);
	int max1=-0x7fffffff,max2=-0x7fffffff,min1=0x7fffffff,min2=0x7fffffff;
	max1=max(max1,findmax(1,1,tot,id[v],en[v]));
	min1=min(min1,findmin(1,1,tot,id[v],en[v]));
	if(id[v]!=1){
		max2=max(max2,findmax(1,1,tot,1,id[v]-1));
		min2=min(min2,findmin(1,1,tot,1,id[v]-1));
	}
	if(en[v]!=n){
		max2=max(max2,findmax(1,1,tot,en[v]+1,n));
		min2=min(min2,findmin(1,1,tot,en[v]+1,n));
	}
	return (ll)max1*(ll)min1+(ll)max2*(ll)min2;
}
int main(){
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)val[i]=read();
	for(int i=1;i<n;i++){
		e[i].u=read();e[i].v=read();
		t[e[i].u].push_back(e[i].v);
		t[e[i].v].push_back(e[i].u);  
	}
	dfs(1,0,1);
	build(1,1,tot);
	for(int i=1;i<=m;i++){
		string c;cin>>c;
		if(c=="QUERY"){
			int p=read();
			ll ans=getans(p);
			printf("%lld\n",ans);
		}
		if(c=="CHANGE"){
			int p=read(),vv=read();
			change(1,1,tot,id[p],id[p],vv);
		}
	}
	return 0;
}