记录编号	305423	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	1.421 s
提交时间	2016-09-10 20:34:03	内存使用	19.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ok 1,1,N
using namespace std;
 
const int maxn=100010*2; 
 
typedef long long LL;
 
int N,Q,cnt,len;
 
struct edge
{
       int from,to;
}e[maxn];
 
struct node
{
       int to,next;
}g[maxn*2];
 
LL mi[maxn<<1],ma[maxn<<1],A[maxn];
 
int dfn[maxn],head[maxn],la[maxn],pos[maxn],fa[maxn],sz[maxn],top[maxn],son[maxn],deep[maxn];
 
 
LL max(LL x,LL y)
{
          if(x<y)return y;
          return x;
}
 
LL min(LL x,LL y)
{
          if(x>y)return y;
          return x;
}
 
void dfs1(int x)
{
     sz[x]=1;
     
     for(int t,i=head[x];i;i=g[i].next)
     {
             t=g[i].to;
             if(!sz[t])
             {
             deep[t]=deep[x]+1;
             dfs1(t);
             sz[x]+=sz[t];
             if(sz[t]>sz[son[x]])son[x]=t;
             }
     }
}
 
void dfs2(int x,int tp)
{
     top[x]=tp;
     dfn[x]=++cnt;
     pos[cnt]=x;
     if(son[x])dfs2(son[x],tp);
     for(int t,i=head[x];i;i=g[i].next)
     {
             t=g[i].to;
             if(!dfn[t])
             dfs2(t,t);
     }
     la[x]=cnt;
}
 
void Build(int rt,int l,int r)
{
     if(l==r)
     {
           mi[rt]=ma[rt]=A[pos[l]];
           //printf("l==%d  data==%lld\n",l,A[pos[l]]);
           return;  
     }
     int mid=(l+r)>>1;
     Build(lson);
     Build(rson);
     mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
     ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
void change(int rt,int l,int r,int s,LL x)
{
     if(l==r)
     {
        mi[rt]=ma[rt]=x;
        return;
     }
     int mid=(l+r)>>1;
     if(s<=mid)change(lson,s,x);
     else change(rson,s,x);
     mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
     ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
     
}
LL queryma(int rt,int l,int r,int s,int t)
{
    if(s<=l&&t>=r)
    {
     return ma[rt];
    }
    int mid=(l+r)>>1;
    if(t<=mid)return queryma(lson,s,t);
    if(s>mid)return queryma(rson,s,t);
    return max(queryma(lson,s,t),queryma(rson,s,t));
}
 
LL querymi(int rt,int l,int r,int s,int t)
{
    if(s<=l&&t>=r)
    {
     return mi[rt];
    }
    int mid=(l+r)>>1;
    if(t<=mid)return querymi(lson,s,t);
    if(s>mid)return querymi(rson,s,t);
    return min(querymi(lson,s,t),querymi(rson,s,t));
}
 
 
void calc(int x)
{
     int ha1=e[x].from,ha2=e[x].to;
     if(dfn[ha1]>dfn[ha2])swap(ha1,ha2);
     LL ans1=0,ansmi=(1ll<<62),ansma=0;
     ans1=querymi(ok,dfn[ha2],la[ha2])*queryma(ok,dfn[ha2],la[ha2]);
         ansmi=min(querymi(ok,1,dfn[ha2]-1),ansmi);
         ansma=max(queryma(ok,1,dfn[ha2]-1),ansma);             
     if(la[ha2]!=N)
     {
         ansmi=min(querymi(ok,la[ha2]+1,N),ansmi);
         ansma=max(queryma(ok,la[ha2]+1,N),ansma);           
     }
     printf("%lld\n",ans1+ansmi*ansma);
}
 
void ADD(int x,int y)
{
    len++;
    g[len].to=y;
    g[len].next=head[x];
    head[x]=len;
}
 
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",&A[i]);
    for(int x,y,i=1;i<N;i++)
    {
            scanf("%d%d",&x,&y);
            e[i].from=x;
            e[i].to=y;
            ADD(x,y);
            ADD(y,x);    
    }
    deep[1]=1;
    dfs1(1);
    dfs2(1,1);
    Build(1,1,N);
    char s[66];
    for(int x,i=1;i<=Q;i++)
    {
            scanf("%s",s);
            if(s[0]=='C')
            {
             LL y;
             scanf("%d%lld",&x,&y);
             change(1,1,N,dfn[x],y);            
            }
            else 
            {
                 scanf("%d",&x);
                 calc(x);
            }
            
    }
    /*fclose(stdin);
    fclose(stdout);*/
    //while(1);
    return 0;
}