Shared code

#include <bits/stdc++.h>
#define endl "\n"
#define pp pair < int ,int >
using namespace std;
typedef long long ll;
const int MAX = 2e5+7;
vector < int > graph[MAX] ;
int head[MAX],big[MAX],depth[MAX],par[MAX],tin[MAX],value[MAX],seg[4*MAX];
int n , q , timer ,sz = 1; 

void update(int k, int x) {
    k += sz; seg[k] = x; k >>= 1;
    while (k > 0) {
        seg[k] = max(seg[2*k], seg[2*k+1]);
        k >>= 1;
    }
}
int query(int a, int b){
    a += sz, b += sz;
    int s = 0;
    while (a <= b) {
        if (a & 1) {
            s = max(s, seg[a]);
            a++;
        }
        if (~b & 1) {
            s = max(s, seg[b]);
            b--;
        }
        a >>= 1, b >>= 1;
    }
    return s;
}
int  dfs(int i,int p){
    int sz = 1;
    int mx_sz = 0;
    par[i] = p;
    for (auto it : graph[i]){
        if (it==p) continue;
        depth[it] = depth[i] + 1 ;
        int curr_sz = dfs(it,i);
        sz+=curr_sz;
        if (mx_sz < curr_sz ) mx_sz = curr_sz , big[i] = it ;
    }
    return sz ;
}   
void hld(int i,int p) {
    head[i] = p ;
    tin[i] = timer++;
    update(tin[i],value[i]);
    if (big[i]) hld(big[i],p);
    for (auto it : graph[i]) {
        if ( it==p || it==par[i] || it==big[i]) continue;
        hld(it,it); // iam the head now 
    }
}
int get_ans(int u,int v){
    int res = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        res = max(res, query(tin[head[u]], tin[u]));
         u = par[head[u]];
    }
    if (depth[u] > depth[v]) swap(u, v);
    res = max(res, query(tin[u], tin[v]));
    return res;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>q;;
    for (int i=1;i<=n;i++){
        cin>>value[i];
    }
    for (int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    while (sz<n) sz*=2;
    dfs(1,1);
    hld(1,1);
  
    while (q--){
        int op;cin>>op;
        if (op==1) {
            int s ,x ; cin>>s>>x;
            value[s] = x ;
            update(tin[s],x);
        }
        else {
            int u,v;cin>>u>>v;
            cout << get_ans(u,v)<<" ";
        }
    }
}