!HLD

#include <bits/stdc++.h>

#define fastRead ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define in(s) freopen(s, "r", stdin)
#define out(s) freopen(s, "w", stdout)

using namespace std;

typedef long long ll;

const int MAXN = 200007, LOG = 21;

vector<int> h, g[MAXN], used, dp, down, p, in, out, intree, num, ind, upper;

vector<vector<int>> arr, tree;

int binup[MAXN][LOG];

int timer = 0;

void build(int i, int v, int l, int r)
{
    if (l == r)
    {
        tree[i][v] = arr[i][l - 1];
        return;
    }
    int med = (r + l) / 2;
    build(i, 2 * v, l, med);
    build(i, 2 * v + 1, med + 1, r);
    tree[i][v] = max(tree[i][2 * v], tree[i][2 * v + 1]);
}

void upd(int i, int v, int l, int r, int q, int hi)
{
    if (r < l || q < l || q > r)
        return;
    if (r == l)
    {
        tree[i][v] = hi;
        return;
    }
    int med = (r + l) / 2;
    upd(i, 2 * v, l, med, q, hi);
    upd(i, 2 * v + 1, med + 1, r, q, hi);
    tree[i][v] = max(tree[i][2 * v], tree[i][2 * v + 1]);
}

int f(int i, int v, int l, int r, int ql, int qr)
{
    if (r < l || ql > r || qr < l)
        return -1e9;
    if (ql <= l && r <= qr)
        return tree[i][v];
    int med = (r + l) / 2;
    return max(f(i, 2 * v, l, med, ql, qr), f(i, 2 * v + 1, med + 1, r, ql, qr));
}

int find_tree(int v, int pr)
{
    int ans = max(h[v], h[pr]);
    while (v != pr)
    {
        if (num[v] == num[pr])
        {
            ans = max(ans, f(num[v], 1, 1, (int)arr[num[v]].size(), ind[pr], ind[v]));
            v = pr;
            continue;
        }
        ans = max(ans, f(num[v], 1, 1, (int)arr[num[v]].size(), 1, ind[v]));
        v = p[upper[v]];
    }
    return ans;
}

bool parent(int u, int p)
{
    return in[p] <= in[u] && out[u] <= out[p];
}

int lca(int v, int u)
{
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (!parent(u, binup[v][i]))
            v = binup[v][i];
    }
    while (!parent(u, v))
        v = p[v];
    return v;
}

int dfs(int v)
{
    in[v] = timer++;
    used[v] = 1;
    dp[v] = 1;
    int maxx = 0, to = -1;
    for (int i = 0; i < (int)g[v].size(); i++)
    {
        int u = g[v][i];
        if (used[u])
            continue;
        int x = dfs(u);
        dp[v] += x;
        p[u] = v;
        if (x > maxx)
        {
            maxx = x;
            to = u;
        }
    }
    down[v] = to;
    out[v] = timer++;
    return dp[v];
}

void dfs1(int v)
{
    used[v] = 1;
    if (!intree[v])
    {
        intree[v] = 1;
        num[v] = (int)arr.size();
        ind[v] = 1;
        upper[v] = v;
        arr.push_back(vector<int>(1, h[v]));
    }
    if (down[v] != -1)
    {
        int u = down[v];
        intree[u] = 1;
        num[u] = num[v];
        ind[u] = ind[v] + 1;
        upper[u] = upper[v];
        arr[num[v]].push_back(h[u]);
    }
    for (int u : g[v])
    {
        if (used[u])
            continue;
        dfs1(u);
    }
}

int main()
{
    assert(in("mail.in"));
    assert(out("mail.out"));
    fastRead;
    int n;
    cin >> n;
    h.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    p.assign(n + 1, -1);
    used.assign(n + 1, 0);
    dp.assign(n + 1, 0);
    down.assign(n + 1, -1);
    in.assign(n + 1, 0);
    out.assign(n + 1, 0);
    p[1] = 1;
    dfs(1);
    for (int i = 1; i <= n; i++)
        binup[i][0] = p[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i <= n; i++)
            binup[i][j] = binup[binup[i][j - 1]][j - 1];
    used.assign(n + 1, 0);
    intree.assign(n + 1, 0);
    num.assign(n + 1, 0);
    upper.assign(n + 1, 0);
    ind.assign(n + 1, 0);
    dfs1(1);
    for (int i = 0; i < (int)arr.size(); i++)
    {
        tree.push_back(vector<int>(5 * (int)arr[i].size() + 100, 0));
        build(i, 1, 1, (int)arr[i].size());
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        char c;
        cin >> c;
        if (c == '?')
        {
            int s, f;
            cin >> s >> f;
            int v = lca(s, f);
            cout << max(find_tree(s, v), find_tree(f, v)) << "\n";
        }
        else
        {
            int v, hi;
            cin >> v >> hi;
            upd(num[v], 1, 1, (int)arr[num[v]].size(), ind[v], hi);
            h[v] = hi;
        }
    }
    return 0;
}