记录编号	340974	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	asddddd	是否通过	通过
代码语言	C++	运行时间	1.239 s
提交时间	2016-11-07 09:39:37	内存使用	7.56 MiB

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define maxn 100010
#define lol long long
using namespace std;
int Basis[maxn],Segmin[4*maxn],Segmax[4*maxn],Pos[maxn],Mark[maxn],n,m,Cost[maxn],Size[maxn],Depth[maxn];
char Ch[10];
struct edge{
	int from,to;
};
edge Edge[maxn];
vector<int>G[maxn];
int sv=0;
void addedge(int from,int to){
	G[from].push_back(to);
	G[to].push_back(from);
}
void build(int l,int r,int o){
	if(l==r){
		Segmax[o]=Segmin[o]=Basis[l];
		Pos[l]=o;
		return ;
	}
	int mid=(l+r)/2;
	build(l,mid,o<<1);
	build(mid+1,r,o<<1|1);
	Segmax[o]=max(Segmax[o<<1],Segmax[o<<1|1]);
	Segmin[o]=min(Segmin[o<<1],Segmin[o<<1|1]);
	return ;
}
int DFS(int u,int pa,int dep){
	Depth[u]=dep;
	Mark[u]=sv;
	Basis[sv]=Cost[u];
	sv++;
	int siz=0;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v!=pa){
			siz+=DFS(v,u,dep+1);
		}
	}
	Size[u]=siz;
	return siz+1;
}
void change(int a,int b){
	int k=Pos[Mark[a]];
	Segmax[k]=Segmin[k]=b;
	k>>=1;
	while(k!=0){
		Segmax[k]=max(Segmax[k<<1],Segmax[k<<1|1]);
		Segmin[k]=min(Segmin[k<<1],Segmin[k<<1|1]);
		k>>=1;
	}
	return;
}
void query(int l,int r,int o,int ll,int rr,lol &maxx,lol &minn){
	if(ll<=l&&rr>=r){
		maxx=max((int)maxx,Segmax[o]);
		minn=min((int)minn,Segmin[o]);
		return;
	}
	int mid=(l+r)/2;
	if(ll<=mid){
		query(l,mid,o<<1,ll,rr,maxx,minn);
	}
	if(rr>mid){
		query(mid+1,r,o<<1|1,ll,rr,maxx,minn);
	}
	return ;
}
void get_input(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&Cost[i]);
	for(int i=0;i<n-1;i++){
		int from,to;
		scanf("%d%d",&from,&to);
		Edge[i].from=from;
		Edge[i].to=to;
		addedge(from,to);
	}
	DFS(1,-1,0);
	build(0,n-1,1);
	for(int i=0;i<m;i++){
		scanf("%s",Ch);
		if(Ch[0]=='C'){
			int a,b;
			scanf("%d%d",&a,&b);
			change(a,b);
		}
		else{
			lol minn1=999999999;lol minn2=999999999;
			lol maxx1=0;lol maxx2=0;
			int u;
			scanf("%d",&u);
			lol from=Edge[u-1].from,to=Edge[u-1].to;
			if(Depth[from]<Depth[to])
			swap(from,to);
			query(0,n-1,1,Mark[from],Mark[from]+Size[from],maxx1,minn1);
			if(Mark[from]!=0)
			query(0,n-1,1,0,Mark[from]-1,maxx2,minn2);
			if(Mark[from]+Size[from]!=n-1)
			query(0,n-1,1,Mark[from]+Size[from]+1,n-1,maxx2,minn2);
			lol asd=minn1*maxx1+minn2*maxx2;
			printf("%lld\n",asd);
		}
	}
}
int main(){
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	ios::sync_with_stdio(false);
	get_input();
}