#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 200000;

class SegmentTree {
public:
    int t[N];
    int n;
    vector<int> a;
    void init(vector<int> v) {
        a = v;
        n = v.size();
        build(1, 0, n - 1);
    }
    void build(int v, int tl, int tr) {
        if (tl == tr)
            t[v] = a[tl];
        else {
            int tm = (tl + tr) >> 1;
            build(v*2, tl, tm);
            build(v*2+1, tm+1, tr);
            t[v] = max(t[v*2], t[v*2+1]);
        }
    }
    int q(int v, int tl, int tr, int l, int r) {
        if (l > r)
            return 0;
        if (tl == l && tr == r)
            return t[v];
        int tm = (tl + tr) >> 1;
        return max(q(v*2, tl, tm, l, min(tm, r)),
                   q(v*2+1, tm+1, tr, max(l, tm+1), r));
    }
    void update(int v, int tl, int tr, int pos, int val) {
        if (tl == tr)
            t[v] = val;
        else {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                update(v*2, tl, tm, pos, val);
            else
                update(v*2+1, tm+1, tr, pos, val);
        }
    }
};
vector<SegmentTree> t;
vector<vector<int> > ch, g, lca;
vector<int> sz, tin, tout, ind, chind, vals;
int root, timer = 0, l;

int dfs(int v, int p = 0) {
    if (g[v].size() == 1 && v != p) {
        return 1;
    }
    int sum = 1;
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (to != p) {
            sum += dfs(to, v);
        }
    }
    sz[v] = sum;
    return sum;
}

void dfs1(int v, int p = 0) {
    tin[v] = ++timer;
    lca[v][0] = p;
    for (int i = 1; i <= l; ++i) {
        lca[v][i] = lca[lca[v][i-1]][i-1];
    }
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (to != p)
            dfs1(to, v);
    }
    tout[v] = ++timer;
}

bool check(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int get_lca(int a, int b) {
    if (check(a, b)){
        return a;
    }
    if (check(b, a))
        return b;
    for (int i = l; i >= 0; --i) {
        if (!check(lca[a][i], b))
            a = lca[a][i];
    }
    return lca[a][0];
}

void hld(int v, int p, vector<int> &curChain) {
    curChain.pb(v);
    ind[v] = curChain.size() - 1;
    chind[v] = ch.size() - 1;
    int sc = -1, maxs = -1;
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (to != p) {
            if (maxs < sz[to]) {
                maxs = sz[to];
                sc = to;
            }
        }
    }
    if (sc == -1)
        return;
    hld(sc, v, curChain);
    for (int i = 0; i < g[v].size(); ++i) {
        int to = g[v][i];
        if (to != p && to != sc) {
            ch.pb(vector<int>());
            hld(to, v, ch[ch.size()-1]);
        }
    }
}

void hld_prepare() {
    t.assign(ch.size(), SegmentTree());
    for (int i = 0; i < ch.size(); ++i) {
        vector<int> v;
        for (int j = 0; j < ch[i].size(); ++j) {
            v.pb(vals[ch[i][j]]);
        }
        t[i].init(v);
    }
}

int ni(int a, int b) {
    int ans = -1;
    int ach, bch;
    while (1) {
        ach = chind[a], bch = chind[b];
        if (ach == bch) {
            int cur = t[ach].q(1, 0, t[ach].n-1, ind[b], ind[a]);
            ans = max(ans, cur);
            break;
        }
        int cur = t[ach].q(1, 0, t[ach].n-1, 0, ind[a]);
        ans = max(ans, cur);
        a = ch[ach][0];
        a = lca[a][0];
    }
    return ans;
}
int ichi(int a, int b) {
    int c = get_lca(a, b);
    return max(ni(a, c), ni(b, c));
}

void san(int v, int val) {
    t[chind[v]].update(1, 0, t[chind[v]].n-1, ind[v], val);
}

int n, m;
void init() {
    g.assign(n, vector<int>());
    sz.assign(n, 0);
    ch.pb(vector<int>());
    l = 1;
    while((1<<l)<=n)++l;
    lca.assign(n, vector<int>(l+1));
    tin.assign(n, 0);
    tout.assign(n, 0);
    ind.assign(n, -1);
    chind.assign(n, -1);
    vals.assign(n, 0);
}

int main() {
    cin >> n;
    m = n - 1;
    init();
    for (int i = 0; i < n; ++i) {
        cin >> vals[i];
    }
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    root = 0;
    dfs(root);
    dfs1(root);
    hld(root, root, ch[0]);
    hld_prepare();
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == '?') {
            cout << ichi(a-1, b-1) << endl;
        }
        else{
            san(a-1, b);
        }
    }
    return 0;
}