TEAMBOOK HLD + быстрый ввод

#include <bits/stdc++.h>
#define long long long
#define all(x) x.begin(), x.end()
using namespace std;

const int BUFFER_SIZE = 1 << 16;
char inBuffer[BUFFER_SIZE], outBuffer[BUFFER_SIZE];
int inLen = 0, inPtr = 0, outPtr = 0;
__attribute__((destructor))
void flushOut() {
    fwrite(outBuffer, 1, outPtr, stdout);
    outPtr = 0;
}
bool canRead() {
    if (inPtr == inLen) {
        inLen = fread(inBuffer, 1, BUFFER_SIZE, stdin);
        inPtr = 0;
    }
    return inPtr < inLen;
}
char peekChar() {
    if (!canRead()) {
        return 0;
    }
    return inBuffer[inPtr++];
}
char getChar() {
    if (!canRead()) {
        return 0;
    }
    return inBuffer[inPtr++];
}
template<class T>
T read();
template<class T>
void write(T);
template<>
char read() {
    char c = getChar();
    while (c == ' ' || c == '\n') {
        c = getChar();
    }
    return c;
}
template<>
int read() {
    int sign = 1, x = 0;
    char c   = read<char>();
    if (c == '-') {
        sign = -1; c = getChar();
    }
    while ('0' <= c && c <= '9') {
        x = 10 * x + c - '0';
        c = getChar();
    }
    return x * sign;
}
void write(char c) {
    if (outPtr == BUFFER_SIZE) {
        flushOut();
    }
    outBuffer[outPtr++] = c;
}
void write(int x) {
    static char s[30];
    int n = 0;
    if (x < 0) {
        write('-');
        x = -x;
    }
    while (!n || x) {
        s[n++] = x % 10 + '0';
        x /= 10;
    }
    while (n--) {
        write(s[n]);
    }
}
void write(long x) {
    static char s[30];
    int n = 0;
    if (x < 0) {
        write('-');
        x = -x;
    }
    while (!n || x) {
        s[n++] = x % 10 + '0';
        x /= 10;
    }
    while (n--) {
        write(s[n]);
    }
}
void write(const char *i) {
    for (; *i; ++i) {
        write(*i);
    }
}
void write() {}
template<class A, class... B>
void write(A a, B... b) {
    write(a);
    write(b...);
}

const int N = 3e5;
vector<int> g[N];
int n, parent[N], sz[N], initH[N], tin[N], tout[N], start[N], timer = 0;

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

void countSize(int v, int p) {
    parent[v] = p;
    sz[v] = 1;
    for (int u : g[v]) {
        if (u == p) {
            continue;
        }
        countSize(u, v);
        sz[v] += sz[u];
    }
}

void precalc(int v, int st, int p) {
    start[v] = st;
    tin[v] = timer++;
    auto it = find(all(g[v]), p);
    if (it != g[v].end()) {
        g[v].erase(it);
    }
    if (g[v].empty()) {
        tout[v] = timer;
        return;
    }
    for (int &u : g[v]) {
        if (sz[u] > sz[g[v].front()]) {
            swap(u, g[v].front());
        }
    }
    precalc(g[v][0], st, v);
    for (int i = 1; i < (int)g[v].size(); ++i) {
        int u = g[v][i];
        precalc(u, u, v);
    }
    tout[v] = timer;
}

int hldTime[N], prefixTime[N];
int st[2 * N];

void treeUpdate(int i, int j) {
    st[i += N] = j;
    for (i >>= 1; i > 0; i >>= 1) {
        st[i] = max(st[2 * i], st[2 * i + 1]);
    }
}

void update(int i, int j) {
    ++timer;
    hldTime[start[i]] = timer;
    treeUpdate(tin[i], j);
}

int treeMax(int l, int r) {
    int res = 0;
    for (l += N, r += N; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) {
            res = max(res, st[l++]);
        }
        if (!(r & 1)) {
            res = max(res, st[r--]);
        }
    }
    return res;
}

int _cnt = 0;
int _sum = 0;
int _helped = 0;
int _full   = 0;

int saved[N];

int prefixQuery(int i) {
    //cerr << "prefix " << i + 1 << endl;
    //if (prefixTime[i] < hldTime[start[i]]) {
        prefixTime[i] = timer;
        saved[i] = treeMax(tin[start[i]], tin[i]);
    //} else {
    //  ++_helped;
    //}
    //++_full;
    return saved[i];
}

int query(int v, int u) {
    ++_cnt;
    int res = 0;
    while (!isAnc(start[v], u)) {
        ++_sum;
        res = max(res, prefixQuery(v));
        v = parent[start[v]];
    }
    while (!isAnc(start[u], v)) {
        ++_sum;
        res = max(res, prefixQuery(u));
        u = parent[start[u]];
    }
    assert(start[v] == start[u]);
    int l = tin[v];
    int r = tin[u];
    if (l > r) {
        swap(l, r);
    }
    ++_sum;
    return max(res, treeMax(l, r));
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    n = read<int>();
    for (int i = 0; i < n; ++i) {
        initH[i] = read<int>();
    }
    for (int u, v, i = 0; i < n - 1; ++i) {
        v = read<int>() - 1;
        u = read<int>() - 1;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    fill_n(prefixTime, N, -1);
    countSize(0, 0);
    precalc(0, 0, 0);
    for (int i = 0; i < n; ++i) {
        st[N + tin[i]] = initH[i];
    }
    for (int i = N - 1; i > 0; --i) {
        st[i] = max(st[2 * i], st[2 * i + 1]);
    }
    int q = read<int>();
    while (q--) {
        char tp = read<char>();
        if (tp == '!') {
            int i = read<int>(), j = read<int>();
            update(i - 1, j);
        } else {
            int i = read<int>(), j = read<int>();
            write(query(i - 1, j - 1), '\n');
        }
    }
    return 0;
}