记录编号	585553	评测结果	AAAAAAAA
题目名称	大话西游	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.256 s
提交时间	2023-12-16 19:32:43	内存使用	10.84 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m,p;
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot,cnt;
int fa[N],son[N],dep[N],size[N];
int dfn[N],rnk[N],top[N] ;
ll a[N];
struct line{
    int x,y;
}li[N];
struct SegentTree{
    int l,r;
	ll mi,ma;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define mi(x) t[x].mi
    #define ma(x) t[x].ma
}t[N<<2];
void pushup(int x){
    mi(x) = min(mi(x<<1),mi(x<<1|1));
    ma(x) = max(ma(x<<1),ma(x<<1|1));
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r){
        mi(x) = ma(x) = a[rnk[l]];
        return;
    }
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void change(int x,int l,ll z){
    if(l(x) == r(x)){
        mi(x) = ma(x) = z;
        return;
    }
    int mid = l(x) + r(x) >>1;
    if(l <= mid)change(x<<1,l,z);
    else change(x<<1|1,l,z);
    pushup(x);
}
ll askmin(int x,int l,int r){
    if(l > r)return INT_MAX;
    if(l <= l(x) && r(x) <= r)return mi(x);
    int mid = l(x) + r(x) >> 1;
    if(r <= mid)return askmin(x<<1,l,r);
    else if(l > mid)return askmin(x<<1|1,l,r);
    else return min(askmin(x<<1,l,r),askmin(x<<1|1,l,r));
}
ll askmax(int x,int l,int r){
    if(l > r)return INT_MIN;
    if(l <= l(x) && r(x) <= r)return ma(x);
    int mid = l(x) + r(x) >> 1;
    if(r <= mid)return askmax(x<<1,l,r);
    else if(l > mid)return askmax(x<<1|1,l,r);
    else return max(askmax(x<<1,l,r),askmax(x<<1|1,l,r));
}
//----------------
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1;
        fa[y] = x;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt;
    rnk[cnt] = x,top[x] = t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
int main(){
    freopen("westward.in","r",stdin);
    freopen("westward.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)scanf("%lld",&a[i]);
    for(int i = 1;i < n;i++){
        int x,y;scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        li[i].x = x,li[i].y = y;
    }
    dep[1] = 1;
    dfs1(1),dfs2(1,1);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        char c[7];ll x,y;
        scanf("%s%lld",c,&x);
        if(c[0] == 'C'){
            scanf("%lld",&y);
            change(1,dfn[x],y);
        }
        else{
            x = dep[li[x].x] < dep[li[x].y]?li[x].y:li[x].x;
            ll ans = 0;
            ans = 1ll * askmin(1,dfn[x],dfn[x]+size[x]-1) * askmax(1,dfn[x],dfn[x]+size[x]-1);
            ans += (min(askmin(1,1,dfn[x]-1),askmin(1,dfn[x]+size[x],n)) * max(askmax(1,1,dfn[x]-1),askmax(1,dfn[x]+size[x],n)));
            printf("%lld\n",ans); 
        }
    }
    
    return 0;
    
}