记录编号	98881	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.816 s
提交时间	2014-04-25 13:36:18	内存使用	33.12 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("westward.in");
ofstream fout("westward.out");
const int SIZEN=200010;
typedef long long ll;
const ll INF=1e17;
class NODE{//树中的线段代表dfs序列中的线段
public:
	int left,right;
	int lc,rc;
	ll mx,mn;//最大最小值
	void clear(void){
		lc=rc=-1;
		left=right=0;
		mx=mn=0;
	}
	NODE(){
		clear();
	}
};
NODE tree[SIZEN*4];
int tot=0;
int N,Q;
ll imp[SIZEN]={0};
vector<int> c[SIZEN];
pair<int,int> edges[SIZEN];
int dfn[SIZEN]={0};
int tim=0;//时间戳
int posnum[SIZEN]={0};//后代数量
int depth[SIZEN]={0};
int dfslis[SIZEN]={0};
void update(int root){
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.lc==-1) return;
	NODE &lson=tree[now.lc],&rson=tree[now.rc];
	now.mx=max(lson.mx,rson.mx);
	now.mn=min(lson.mn,rson.mn);
}
int build(int x,int y){
	int p=tot++;
	NODE &now=tree[p];
	now.left=x,now.right=y;
	if(x<y){
		int mid=(x+y)/2;
		now.lc=build(x,mid);
		now.rc=build(mid+1,y);
		update(p);
	}
	else{//这个点代表dfs序列的第x项
		now.lc=now.rc=-1;
		now.mx=now.mn=imp[dfslis[x]];
	}
	return p;
}
void change(int root,int x,ll t){//点x的权值改成t(x指dfs序列的第x项)
	if(root==-1) return;
	NODE &now=tree[root];
	if(now.left>x||now.right<x) return;//不相交
	if(now.left==x&&now.right==x){//恰好是这个点
		now.mx=now.mn=t;
	}
	else{
		change(now.lc,x,t);
		change(now.rc,x,t);
		update(root);
	}
}
pair<ll,ll> getlis(int root,int x,int y){//[x,y]的最大值和最小值,分别是first和second
	if(root==-1) return make_pair(0,INF);
	NODE &now=tree[root];
	if(now.left>y||now.right<x) return make_pair(0,INF);
	if(now.left>=x&&now.right<=y) return make_pair(now.mx,now.mn);
	pair<int,int> w1,w2;
	w1=getlis(now.lc,x,y);
	w2=getlis(now.rc,x,y);
	return make_pair(max(w1.first,w2.first),min(w1.second,w2.second));
}
void change(int x,ll t){//把第x个节点的权值改成t
	change(0,dfn[x],t);
}
ll query(int x){//把第x条边删掉后的结果
	//断开的下面的那个点是edges[x].second
	int u=edges[x].first,v=edges[x].second;
	//u在上面v在下面
	pair<ll,ll> w1,w2,t1,t2;
	w1=getlis(0,dfn[v],dfn[v]+posnum[v]-1);
	t1=getlis(0,1,dfn[v]-1);
	t2=getlis(0,dfn[v]+posnum[v],N);
	w2=make_pair(max(t1.first,t2.first),min(t1.second,t2.second));
	//w1是part1的值,w2是part2的值
	return w1.first*w1.second+w2.first*w2.second;
}
void work(void){
	//edges数组中,first应当存上面的,second应当存下面的
	for(int i=1;i<=N-1;i++) if(depth[edges[i].first]>depth[edges[i].second]) swap(edges[i].first,edges[i].second);
	char cmd[255]={0};
	int x;
	ll w;
	for(int i=1;i<=Q;i++){
		fin>>cmd;
		if(cmd[0]=='C'){
			fin>>x>>w;
			change(x,w);
		}
		else if(cmd[0]=='Q'){
			fin>>x;
			fout<<query(x)<<endl;
		}
	}
}
void DFS(int x,int f){
	tim++;
	dfn[x]=tim,dfslis[tim]=x;
	for(int i=0;i<c[x].size();i++){
		int u=c[x][i];
		if(u!=f){
			depth[u]=depth[x]+1;
			DFS(u,x);
			posnum[x]+=posnum[u];
		}
	}
	posnum[x]++;
}
void read(void){
	//scanf("%d%d",&N,&Q);
	fin>>N>>Q;
	//for(int i=1;i<=N;i++) scanf("%lld",&imp[i]);
	for(int i=1;i<=N;i++) fin>>imp[i];
	int u,v;
	for(int i=1;i<=N-1;i++){
		//scanf("%d%d",&u,&v);
		fin>>u>>v;
		edges[i]=make_pair(u,v);
		c[u].push_back(v);
		c[v].push_back(u);
	}
}
int main(){
	//freopen("westward.in","r",stdin);
	//freopen("westward.out","w",stdout);
	read();
	DFS(1,0);
	build(1,N);
	work();
	fin.close();
	fout.close();
	return 0;
}