#define _CRT_SECURE_NO_WARNINGS
#define debug(l) cerr<<#l<<' '<<l<<'\n';
#include "bits/stdc++.h"
using namespace std;
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
vector<vector<int>> gr;
vector<int> head, siz, tin, tout, w, parent, a;
const int inf = INT_MAX;
struct segtree {
    vector<int> t;
    int n;
    segtree() {}
    void init(int _n) {
        n = _n;
        t.resize(4 * n + 100, -inf);
    }
    void build(int v, int tl, int tr, vector<int>& a) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm, a);
        build(v * 2 + 1, tm + 1, tr, a);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
    void upd(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) {
            t[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            upd(v * 2, tl, tm, pos, val);
        }
        else {
            upd(v * 2 + 1, tm + 1, tr, pos, val);
        }
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
    int get_mx(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l) {
            return -INT_MAX;
        }
        if (tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return max(get_mx(v * 2, tl, tm, l, r), get_mx(v * 2 + 1, tm + 1, tr, l, r));
    }
};
int t = 0;
void dfs1(int v, int p) {
    siz[v] = 1;
    for (int& u : gr[v]) {
        if (u == p) {
            swap(u, gr[v].back());
            gr[v].pop_back();
            break;
        }
    }
    parent[v] = (p == -1 ? v : p);
    for (int& u : gr[v]) {
        dfs1(u, v);
        siz[v] += siz[u];
        if (siz[u] > siz[gr[v][0]]) {
            swap(gr[v][0], u);
        }
    }
}
void dfs2(int v) {
    tin[v] = t++;
    a.push_back(w[v]);
    for (int& u : gr[v]) {
        if (u == gr[v][0]) {
            head[u] = head[v];
        }
        else {
            head[u] = u;
        }
        dfs2(u);
    }
    tout[v] = t;
}
segtree Euler;
void upd(int v, int val) {
    Euler.upd(1, 0, Euler.n - 1, tin[v], val);
}
bool is_in_sector(int u, int v) {
    return tin[u] <= tin[v] && tin[v] < tout[u];
}
void up(int& u, int& v, int& ans) {
    while (!is_in_sector(head[u], v)) {
        ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[head[u]], tin[u]));
        u = parent[head[u]];
    }
}
int get_max(int u, int v) {
    int ans = -inf;
    up(u, v, ans);
    up(v, u, ans);
    if (!is_in_sector(u, v)) {
        swap(u, v);
    }
    ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[u], tin[v]));
    return ans;
}
signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    gr.resize(n), tin.resize(n), tout.resize(n), siz.resize(n), w.resize(n), head.resize(n), parent.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    dfs1(0, -1);
    dfs2(0);
    Euler.init((int)a.size());
    Euler.build(1, 0, Euler.n - 1, a);
    int q;
    cin >> q;
    while (q--) {
        char indef;
        cin >> indef;
        if (indef == '?') {
            int u, v;
            cin >> u >> v;
            u--, v--;
            cout << get_max(u, v) << '\n';
        }
        if (indef == '!') {
            int v, x;
            cin >> v >> x;
            v--;
            upd(v, x);
        }
    }
}