记录编号	99364	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.596 s
提交时间	2014-04-27 14:46:57	内存使用	9.49 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<deque>
using namespace std;
const long long INF=100000001;
int N,Q;
long long importance[100010];
vector <int> p[100010];
int tot=0;
int dfn[100010];
int back[100010];
int len[100010];
class EDGE
{
public:
	int u,v;
};
vector <EDGE> E;
void dfs(int x,int bef)
{
	dfn[x]=++tot;
	back[tot]=x;
	len[x]=1;
	for(unsigned int i=0;i<p[x].size();i++)
	{
		if(bef==p[x][i])continue;
		dfs(p[x][i],x);
		len[x]+=len[p[x][i]];
	}
}
class SEG
{
public:
	int l,r,Lc,Rc;
	long long mini,maxi;
}tree[201000];
void update(int root)
{
	if(tree[root].Lc==-1)return;
	tree[root].mini=min(tree[tree[root].Lc].mini,tree[tree[root].Rc].mini);
	tree[root].maxi=max(tree[tree[root].Lc].maxi,tree[tree[root].Rc].maxi);
}
void Build(int root,int l,int r)
{
	tree[root].l=l;
	tree[root].r=r;
	if(l==r)
	{
		tree[root].maxi=tree[root].mini=importance[back[l]];
		tree[root].Lc=tree[root].Rc=-1;
		return;
	}
	int mid=(l+r)>>1;
	tree[root].Lc=++tot;
	Build(tot,l,mid);
	tree[root].Rc=++tot;
	Build(tot,mid+1,r);
	update(root);
}
void Insert(int root,int k,long long w)
{
	//pushdown(root);
	if(tree[root].l>k || tree[root].r<k)return;
	if(tree[root].Lc==-1)
	{
		tree[root].maxi=tree[root].mini=w;
		return;
	}
	Insert(tree[root].Lc,k,w);
	Insert(tree[root].Rc,k,w);
	update(root);
}
pair<long long,long long> Segment(int root,int l,int r)
{
	//pushdown(root);
	if(l>r)return make_pair(INF,0);
	if(tree[root].l>r || tree[root].r<l)return make_pair(INF,0);
	if(tree[root].l>=l && tree[root].r<=r)
	{
		return make_pair(tree[root].mini,tree[root].maxi);
	}
	pair<long long,long long> left,right;
	left=Segment(tree[root].Lc,l,r);
	right=Segment(tree[root].Rc,l,r);
	update(root);
	return make_pair(min(left.first,right.first),max(left.second,right.second));
}
int main()
{
	freopen("westward.in","r",stdin);
	freopen("westward.out","w",stdout);
	scanf("%d %d",&N,&Q);
	for(int i=1;i<=N;i++)scanf("%lld",&importance[i]);
	int u,v;
	for(long long i=1;i<N;i++)
	{
		scanf("%d %d",&u,&v);
		E.push_back((EDGE){u,v});
		p[u].push_back(v);
		p[v].push_back(u);
	}
	tot=0;
	dfs(1,-1);
	tot=0;
	Build(0,1,N);
	char tmp[10];
	int x;
	long long y;
	long long Ans;
	for(int i=1;i<=Q;i++)
	{
		scanf("%s",tmp);
		if(tmp[0]=='C')
		{
			scanf("%d %lld",&x,&y);
			Insert(0,dfn[x],y);
		}
		else
		{
			scanf("%d",&x);
			int v1,v2;
			v1=E[x-1].u;v2=E[x-1].v;
			if(len[v1]<len[v2])swap(v1,v2);
			pair<long long,long long> ans[2],temp[2];
			ans[0]=Segment(0,dfn[v2],dfn[v2]+len[v2]-1);
			temp[0]=Segment(0,1,dfn[v2]-1);
			temp[1]=Segment(0,dfn[v2]+len[v2],N);
			ans[1]=make_pair(min(temp[0].first,temp[1].first),max(temp[0].second,temp[1].second));
			Ans=ans[0].first*ans[0].second+ans[1].first*ans[1].second;
			//printf("%lld %lld %lld %lld  ",ans[0].first,ans[0].second,ans[1].first,ans[1].second);
			printf("%lld\n",Ans);
		}
	}
	return 0;
}