Link to this code: https://cses.fi/paste/0294b268ed51c6625a2a9b/
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define BigInt      __int128
#define endl        '\n'
#define mii         map<ll int,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define hell        1000000007

using namespace std;

#define N  200005

int arr[N];
int a[N],seg[N<<2];
void build(int node,int start,int end){
    if(start==end){
        seg[node]=a[start];
        return;
    }
    int mid=(start+end)>>1;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    seg[node]=max(seg[node<<1], seg[node<<1|1]);
}
int query(int node,int start,int end,int l,int r){
    if(l<=start && r>=end) return seg[node];
    if(r<start || l>end) return 0;
    int mid=(start+end)>>1;
    int ans1=query(node<<1,start,mid,l,r);
    int ans2=query(node<<1|1,mid+1,end,l,r);
    return max(ans1,ans2);
}
void update(int node,int start,int end,int x,int val){
    if(start==end){
        a[x]=val;
        seg[node]=val;
        return;
    }
    int mid=(start+end)>>1;
    if(start<=x && x<=mid) update(node<<1,start,mid,x,val);
    else update(node<<1|1,mid+1,end,x,val);
    seg[node]=max(seg[node<<1], seg[node<<1|1]);
}


class HeavyLight {
    struct Node {
        int jump, subsize, depth, lin, parent;
        vector<int> leg;
    };
    vector<Node> T;
    bool processed = false;
public:
    HeavyLight(int n) : T(n) {}
    void AddEdge(int a, int b) {
        T[a].leg.push_back(b);
        T[b].leg.push_back(a);
    }
    void Preprocess() {
        dfs_sub(0, -1);
        dfs_jump(0, 0);
        processed = true;
    }
    // Gets the position in the HL linearization
    int GetPosition(int node) {
        assert(processed);
        return T[node].lin;
    }
    // Gets an array of ranges of form [li...ri)
    // that correspond to the ranges you would need
    // to query in the underlying structure
    vector<pair<int, int>> GetPathRanges(int a, int b) {
        assert(processed);
        vector<pair<int, int>> ret;
        while (T[a].jump != T[b].jump) {
            if (T[T[a].jump].depth < T[T[b].jump].depth)
                swap(a, b);
            ret.emplace_back(T[T[a].jump].lin, T[a].lin + 1);
            a = T[T[a].jump].parent;
        }
        if (T[a].depth < T[b].depth) swap(a, b);
        ret.emplace_back(T[b].lin, T[a].lin + 1);
        return ret;
    }
private:
    int dfs_sub(int x, int par) {
        auto &node = T[x];
        node.subsize = 1;
        node.parent = par;
        if (par != -1) {
            node.leg.erase(find(node.leg.begin(), node.leg.end(), par));
            node.depth = 1 + T[par].depth;
        }
        for (auto vec : node.leg)
            node.subsize += dfs_sub(vec, x);
        return node.subsize;
    }
    int timer = 0;
    void dfs_jump(int x, int jump) {
        auto &node = T[x];
        node.jump = jump;
        node.lin = timer++;
        iter_swap(node.leg.begin(), max_element(node.leg.begin(), node.leg.end(),
            [&](int a, int b) { return T[a].subsize < T[b].subsize; }));
        for (auto vec : node.leg)
            dfs_jump(vec, vec == node.leg.front() ? jump : vec);
    }
};



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int TESTS=1;
    // cin>>TESTS;
    while(TESTS--)
    {
        int n, q;
        cin >> n >> q;
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        HeavyLight graph(n);
        int m = n - 1;
        while(m--) {
            int x, y;
            cin >> x >> y;
            x--;y--;
            graph.AddEdge(x, y);
        }
        graph.Preprocess();
        int maxi = 0;
        for(int i = 1; i <= n; i++) {
            int idx = graph.GetPosition(i - 1) + 1;
            maxi = max(maxi, idx);
            a[idx] = arr[i];
        }
        build(1, 1, maxi);
        while(q--) {
            int t;
            cin >> t;
            if(t == 1) {
                int i, x;
                cin >> i >> x;
                int idx = graph.GetPosition(i - 1) + 1;
                update(1, 1, maxi, idx, x);
            }
            else {
                int a, b;
                cin >> a >> b;
                a--;b--;
                vector<pair<int, int>> v = graph.GetPathRanges(a, b);
                int ans = 0;
                for(auto path : v) {
                    ans = max(ans, query(1, 1, maxi, path.F + 1, path.S));
                }
                cout << ans << " ";
            }
        }
    }
    return 0;
}