//// @author s_k_a_r_a
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#ifdef Local
#include "debug.h"
#else
#define debug(...)
#endif

#define int long long

typedef long long ll;
typedef long double ld;

#define vec vector
#define str string
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;

namespace st {
#ifdef Local
static const int N = 4;
#else
static const int N = 64 * 1024;
#endif
int tree[2 * N - 1]{};

int iq, dq;

void upd(int i, int l, int r) {
    if (r - l == 1)
        tree[i] = dq;
    else {
        int m = (l + r) / 2;
        if (iq < m)
            upd(2 * i + 1, l, m);
        else
            upd(2 * i + 2, m, r);
        tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
    }
}

void upd(int i, int d) {
    iq = i, dq = d;
    upd(0, 0, N);
}

int lq, rq;

int get(int i, int l, int r) {
    if (lq <= l && r <= rq)
        return tree[i];
    int m = (l + r) / 2;
    int res = 0;
    if (lq < m)
        res = max(res, get(2 * i + 1, l, m));
    if (m < rq)
        res = max(res, get(2 * i + 2, m, r));
    return res;
}

int get(int l, int r) {
    lq = l, rq = r + 1;
    return get(0, 0, N);
}
}  // namespace st

static const int N = 50050;
vec<int> g[N];
int sz[N];

void stdfs(int v, int p = -1) {
    sz[v] = 1;
    if (g[v].front() == p && sz(g[v]) > 1)
        swap(g[v][0], g[v][1]);
    for (int& u : g[v])
        if (u != p) {
            stdfs(u, v), sz[v] += sz[u];
            if (sz[u] > sz[g[v].front()])
                swap(g[v][0], u);
        }
}

int tin[N], tout[N], t = 0, depth[N], head[N], par[N];
vec<int> eu;

void eubuild(int v, int p = -1, int h = -1) {
    tin[v] = t++;
    par[v] = p;
    eu.pb(v);
    if (p == -1)
        p = v;
    depth[v] = depth[p] + 1;
    if (h == -1)
        h = v;
    head[v] = h;
    int k = g[v].front();
    if (k != p)
        eubuild(k, v, h);
    for (int& u : g[v])
        if (u != p && u != k)
            eubuild(u, v);
    tout[v] = t;
}

bool ispar(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

void solve() {
    int n;
    cin >> n;
    vec<int> h(n);
    for (int& i : h)
        cin >> i;
    if (n == 1) {
        int q;
        cin >> q;
        char mode;
        for (int v, hp; q--;) {
            cin >> mode >> v >> hp;
            if (mode == '!')
                h[0] = hp;
            else
                cout << h[0] << '\n';
        }
        return;
    }
    for (int i = 0, v, u; i < n - 1; i++) {
        cin >> v >> u, v--, u--;
        g[v].pb(u), g[u].pb(v);
    }
    stdfs(0);
    eubuild(0);
    debug(eu);
    for (int i = 0, v; i < n; i++) {
        v = eu[i];
        st::upd(i, h[v]);
    }
    int q;
    cin >> q;
    char mode;
    for (int v, u, hp, res; q--;) {
        cin >> mode >> v, v--;
        if (mode == '!') {
            cin >> hp;
            h[v] = hp;
            st::upd(tin[v], hp);
        } else {
            cin >> u, u--;
            res = 0;
            while (!ispar(head[v], u)) {
                if (head[v] == v)
                    res = max(res, h[v]), v = par[v];
                else
                    res = max(res, st::get(tin[head[v]], tin[v])), v = par[head[v]];
            }
            while (!ispar(head[u], v)) {
                if (head[u] == u)
                    res = max(res, h[u]), u = par[u];
                else
                    res = max(res, st::get(tin[head[u]], tin[u])), u = par[head[u]];
            }
            if (depth[v] < depth[u])
                res = max(res, st::get(tin[v], tin[u]));
            else
                res = max(res, st::get(tin[u], tin[v]));
            cout << res << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;
    //    cin >> tt;
    while (tt--)
        solve();

    return 0;
}