#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("westward.in", "r", stdin);
auto OUT = freopen("westward.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 1e5 + 5;
int n = mread(), q = mread(), a[N], dfn[N], siz[N], d[N], b[N], idx;
vector<int> v[N];
pair<int, int> ed[N];
struct node{
    int ma[N << 2], mi[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]);
        return;
    }
    void build(int x, int nl, int nr){
        ma[x] = LONG_LONG_MIN;
        mi[x] = LONG_LONG_MAX;
        if(nl == nr){
            ma[x] = mi[x] = b[nl];
            return;
        }
        int mid = nl + nr >> 1;
        build(x << 1, nl, mid);
        build(x << 1 | 1, mid + 1, nr);
        pushup(x);
        return;
    }
    void ch(int x, int nl, int nr, int p, int k){
        if(nl == nr){
            ma[x] = mi[x] = k;
            return;
        }
        int mid = nl + nr >> 1;
        if(p <= mid){
            ch(x << 1, nl, mid, p, k);
        }
        else{
            ch(x << 1 | 1, mid + 1, nr, p, k);
        }
        pushup(x);
        return;
    }
    pair<int, int> query(int x, int nl, int nr, int l, int r){
        if(nl >= l && nr <= r){
            return mp(mi[x], ma[x]);
        }
        int mid = nl + nr >> 1;
        auto ans = mp(LONG_LONG_MAX, LONG_LONG_MIN);
        if(mid >= l){
            ans = query(x << 1, nl, mid, l, r);
        }
        if(mid + 1 <= r){
            auto tmp =query(x << 1 | 1, mid + 1, nr, l, r);
            ans.fi = min(ans.fi, tmp.fi);
            ans.se = max(ans.se, tmp.se);
        }
        return ans;
    }
}tr;
void dfs(int x, int fa){
    d[x] = d[fa] + 1;
    siz[x] = 1;
    dfn[x] = ++idx;
    for(int y : v[x]){
        if(y == fa){
            continue;
        }
        dfs(y, x);
        siz[x] += siz[y];
    }
    return;
}
signed main(){
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int i = 1, x, y; i < n; i ++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        ed[i] = mp(x, y);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i ++){
        b[dfn[i]] = a[i];
    }
    tr.build(1, 1, n);
    while(q --){
        string op;
        cin >> op;
        if(op == "CHANGE"){
            int x = mread(), w = mread();
            tr.ch(1, 1, n, dfn[x], w);
        }
        else{
            int id = mread();
            int x = ed[id].fi, y = ed[id].se;
            if(d[x] < d[y]){
                swap(x, y);
            }
            auto t1 = tr.query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1),
            t2 = tr.query(1, 1, n, 1, dfn[x] - 1),
            t3 = tr.query(1, 1, n, dfn[x] + siz[x], n);
            printf("%lld\n", t1.fi * t1.se + min(t2.fi, t3.fi) * max(t2.se, t3.se));
        }
    }
    return 0;
}