记录编号	305297	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.504 s
提交时间	2016-09-10 19:23:52	内存使用	98.39 MiB

#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define LL long long
using namespace std;
const LL maxn=1050000;
struct Edge{
    LL from,to,next;
}e[maxn];
struct Node{
    LL max,min;
}a[maxn];
LL deep[maxn],son[maxn],size[maxn],top[maxn],id[maxn],pos[maxn];
LL root[maxn],head[maxn],len,n,m,v[maxn],cnt;
void Insert(LL x,LL y){
    len++;e[len].to=y;e[len].from=x;e[len].next=head[x];head[x]=len;
}
void Dfs1(LL x){
    size[x]=1;
    for(LL i=head[x];i;i=e[i].next){
        LL j=e[i].to;
        if(root[x]!=j){
            root[j]=x;deep[j]=deep[x]+1;
            Dfs1(j);
            size[x]+=size[j];
            if(size[j]>size[son[x]])son[x]=j;
        }
    }
}
void Dfs2(LL x,LL tp){
    top[x]=tp;id[x]=++cnt;pos[cnt]=x;
    if(son[x])Dfs2(son[x],tp);
    for(LL i=head[x];i;i=e[i].next){
        LL j=e[i].to;
        if(root[x]!=j && son[x]!=j)Dfs2(j,j); 
    }
}
void Build(LL rt,LL l,LL r){
    if(l==r){
        a[rt].min=a[rt].max=v[pos[l]];
        return;
    }
    LL mid=(l+r)>>1;
    Build(lson);Build(rson);
    a[rt].min=min(a[rt<<1].min,a[rt<<1|1].min);
    a[rt].max=max(a[rt<<1].max,a[rt<<1|1].max); 
}
void Change(LL x,LL z,LL rt,LL l,LL r){
    if(l==r){
        a[rt].max=a[rt].min=z;return; 
    } 
    LL mid=(l+r)>>1;
    if(x<=mid)Change(x,z,lson);
    else Change(x,z,rson);
    a[rt].min=min(a[rt<<1].min,a[rt<<1|1].min);
    a[rt].max=max(a[rt<<1].max,a[rt<<1|1].max); 
}
LL Get_max(LL s,LL t,LL rt,LL l,LL r){
    if(s<=l && t>=r)return a[rt].max;
    LL mid=(l+r)>>1;
    if(t<=mid)return Get_max(s,t,lson);
    if(s>mid)return Get_max(s,t,rson);
    return max(Get_max(s,t,lson),Get_max(s,t,rson));
}
LL Get_min(LL s,LL t,LL rt,LL l,LL r){
    if(s<=l && t>=r)return a[rt].min;
    LL mid=(l+r)>>1;
    if(t<=mid)return Get_min(s,t,lson);
    if(s>mid)return Get_min(s,t,rson);
    return min(Get_min(s,t,lson),Get_min(s,t,rson));
}
void Init();
int main(){
    freopen("westward.in","r",stdin);
    freopen("westward.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
     scanf("%lld%lld",&n,&m);
     for(LL i=1;i<=n;i++)scanf("%lld",&v[i]);
     for(LL i=1;i<n;i++){
         LL x,y;scanf("%lld%lld",&x,&y);
         Insert(x,y);Insert(y,x);
     } 
     deep[1]=1;
     Dfs1(1);Dfs2(1,1);Build(1,1,n);
     for(LL i=1;i<=m;i++){
         char s[10];scanf("%s",s);
         if(s[0]=='C'){LL x,y;scanf("%lld%lld",&x,&y);Change(id[x],y,1,1,n);}
         else {
             LL k;scanf("%lld",&k);
             k=2*k-1;
             LL x,fo=e[k].from,to=e[k].to;
             if(root[fo]==to)x=fo;
             else x=to;
             //printf("<<%d %d %d>>\n",x,id[x],id[x]+size[x]-1);
             LL min1=Get_min(id[x],id[x]+size[x]-1,1,1,n),max1=Get_max(id[x],id[x]+size[x]-1,1,1,n);
             LL min2=0,max2=0;
             if(1<=id[x]-1 && id[x]+size[x]<=n)min2=min(Get_min(1,id[x]-1,1,1,n),Get_min(id[x]+size[x],n,1,1,n));
             else if(1<=id[x]-1)min2=Get_min(1,id[x]-1,1,1,n);
             else min2=Get_min(id[x]+size[x],n,1,1,n);
             //system("pause");
             if(1<=id[x]-1 && id[x]+size[x]<=n)max2=max(Get_max(1,id[x]-1,1,1,n),Get_max(id[x]+size[x],n,1,1,n));
             else if(1<=id[x]-1)max2=Get_max(1,id[x]-1,1,1,n);
             else max2=Get_max(id[x]+size[x],n,1,1,n);
             
             //LL max2=max(Get_max(1,id[x]-1,1,1,n),Get_max(id[x]+size[x],n,1,1,n));
             printf("%lld\n",min1*max1+min2*max2);
         }
     } 
}