path queries 2

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll nmax = 1e9+7;
const ll nmax2 = 998244353;

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    ll n, q;
    std::cin >> n >> q;

    std::vector<ll> a(n + 1);
    for (ll i = 1; i <= n; i++) std::cin >> a[i];

    std::vector<ll> adj[n + 1];
    for (ll i = 1, x, y; i < n; i++){
        std::cin >> x >> y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    std::vector<ll> sz(n + 1), depth(n + 1), par(n + 1);
    std::function<ll(ll, ll)> dfs = [&] (ll u, ll p){
        par[u] = p;
        sz[u] = 1;
        for (auto v: adj[u]){
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            sz[v] += dfs(v, u);
        }
        return sz[u];
    };
    auto waste = dfs(1, 1);

    ll cnt = 1;
    std::vector<ll> id(n + 1), tp(n + 1), st(2 * n + 5);

    std::function<void(ll, ll)> update = [&] (ll ind, ll val){
        for (st[ind += n - 1] = val; ind > 1; ind >>= 1) st[ind >> 1] = std::max(st[ind], st[ind ^ 1]);
    };

    std::function<void(ll, ll, ll)> dfs_hld = [&] (ll u, ll p, ll top){
        id[u] = cnt++;
        tp[u] = top;

        update(id[u], a[u]);
        ll heavy_child = -1, heavy_size = -1;
        for (auto v : adj[u]){
            if (v == p) continue;
            if (sz[v] > heavy_size){
                heavy_size = sz[v];
                heavy_child = v;
            }
        }

        if (heavy_size == -1) return;
        dfs_hld(heavy_child, u, tp[u]);

        for (auto v: adj[u]){
            if (v == p or v == heavy_child) continue;
            dfs_hld(v, u, v);
        }
    };
    dfs_hld(1, 1, 1);

    std::function<ll(ll, ll)> query = [&] (ll low, ll high){
        ll ra = 0, rb = 0;
        for (low += n - 1, high += n - 1; low < high; low >>= 1, high >>= 1){
            if (low & 1) ra = std::max(ra, st[low++]);
            if (high & 1) rb = std::max(rb, st[--high]);
        }
        return std::max(low, high);
    };

    std::function<ll(ll, ll)> path = [&] (ll x, ll y){
        ll res = 0;
        while (tp[x] != tp[y]){
            if (depth[tp[x]] < depth[tp[y]]) std::swap(x, y);
            res = std::max(res, query(id[tp[x]], id[x]));
            x = par[tp[x]];
        }

        if (depth[x] > depth[y]) std::swap(x, y);
        res = std::max(res, query(id[x], id[y]));
        return res;
    };

    for (ll i = n - 1; i > 0; i--) st[i] = std::max(st[i << 1], st[i << 1 | 1]);

    for (ll i = 1, x, y, z; i <= q; i++){
        std::cin >> x >> y >> z;
        if (x == 1){
            a[y] = z;
            update(id[y], z);
        } else if (x == 2){
            std::cout << path(y, z) << '\n';
        }
    }
}