Shared code

#include <iostream>
#include <vector>
 
using namespace std;
 
const int NEUTRO = 0;
 
inline int log2_floor(const int &  num){
    return __builtin_clzll(1LL) - __builtin_clzll(num);
}
 
inline int log2_ceil(const int &  num){
    return log2_floor(num) + (__builtin_popcountll(num) > 1);
}
 
inline int L(const int &  i){
    return 2*i;
}
 
inline int R(const int &  i){
    return 2*i+1;
}
 
struct segment_tree {// for maximum
    int N, numElements;
    vector<int> seg, vec;
 
    segment_tree() = default;
 
    void add(const int & num){
        vec.push_back(num);
    }
 
    void init(){
        numElements = vec.size();
        int lg = log2_ceil(numElements);
        N = (1LL << lg);
 
        seg.assign(2*N+1, -NEUTRO);
        for (int i=0; i<numElements; ++i){
            seg[N+i] = vec[i];
        }
 
        for (int i=N-1; i>=1; --i){
            seg[i] = max(seg[L(i)], seg[R(i)]);
        }
    }
 
    void set(int pos, const int &  val){ // 0-indexed
        vec[pos] = val;
 
        pos = N+pos;
        seg[pos] = val; pos /= 2;
 
        while (pos >= 1){
            seg[pos] = max(seg[L(pos)], seg[R(pos)]);
            pos /= 2;
        }
    }
 
    int get(const int &  node, const int &  l, const int &  r, const int &  a, const int &  b){
        if (b < l || r < a) return -NEUTRO;
 
        if (a <= l && r <= b){
            return seg[node];
        }
 
        int m = (l+r)/2;
        int res = -NEUTRO;
        if (a <= m){
            res = max(res, get(L(node), l, m, a, b));
        } 
        if (b >= m+1){
            res = max(res, get(R(node), m+1, r, a, b));
        }
 
        return res;
    }
 
    int get(const int &  l, const int &  r){
        return get(1, 0, N-1, l, r);
    }
};
 
const int rt=1;
const int N = 2e5+67;
const int M = 18;
int S, SD;
int t;
 
vector<int> G[N];
int par[N][M+1];
int val[N], tIn[N], tOut[N], subSz[N];
 
segment_tree heavyPaths;
int pathStart[N], pathPos[N];
 
int dfsRoot(const int & i, const int & p){
    par[i][0] = p;
 
    tIn[i] = t++;
    int sum = 1;
    for (int j : G[i]){
        if (j == p) continue;
 
        sum += dfsRoot(j, i);
    }
    tOut[i] = t++;
 
    return subSz[i] = sum;
}
 
inline bool isPar(const int &  p, const int &  s){
    return (tIn[p] <= tIn[s] && tOut[s] <= tOut[p]);
}
 
int LCA(const int &  x, const int &  y){ 
    if (isPar(x, y)){
        return x;
    } else if (isPar(y, x)){
        return y;
    }
 
    int res=x;
    for (int j=SD; j>=0; --j){
        int nw = par[res][j];
        if (!isPar(nw, y)){
            res = nw;
        }
    }
    return par[res][0];
}
 
int findHeavy(const int & i){
    int mx=-1, res=-1;
    for (const int & j : G[i]){
        if (j == par[i][0]) continue;
 
        if (subSz[j] > mx) {
            res = j;
            mx = subSz[j];
        }
    }
 
    return res;
}
 
int K=0;
void dfsHeavy(const int & i, bool heavy){ 
    int p = par[i][0];
    
    if (heavy){
        pathStart[i] = pathStart[p];
    } else {
        pathStart[i] = i;
        pathPos[i] = 0;
    }
    pathPos[i] = K++;
    heavyPaths.add(val[i]);
    
    int mxJ = findHeavy(i);
    
    if (mxJ == -1){
        return;
    }
 
    dfsHeavy(mxJ, true);
 
    for (int j : G[i]){
        if (j == p || j == mxJ) continue;
 
        dfsHeavy(j, false);
    }
}
 
int maxUpPath(int &p, int &x){
    int res=-NEUTRO; 
 
    while (pathStart[p] != pathStart[x]){
        int y = pathStart[x];
        int l = pathPos[y], r = pathPos[x];
 
        res = max(res, heavyPaths.get(l, r));
        
        x = par[y][0];
    }
 
    int l = pathPos[p], r = pathPos[x]; 
    res = max(res, heavyPaths.get(l,r));
 
    return res;
}
 
void solve(){
    int Q; cin >> S >> Q;
    SD = log2_floor(S);
 
    for (int i=1; i<=S; ++i){
        cin >> val[i];
    }
 
    for (int i=0; i<S-1; ++i){
        int u, v; cin >> u >> v;
 
        G[u].push_back(v);
        G[v].push_back(u);
    }
 
    t=0;
    dfsRoot(rt, rt);
 
    for (int j=1; j<=SD; ++j){
        for (int i=1; i<=S; ++i){
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
 
    K=0;
    dfsHeavy(rt, false);
    heavyPaths.init();
 
    while (Q--){
        int typ; cin >> typ;
 
        if (typ == 1){
            int s, x; cin >> s >> x;
            val[s] = x;
            heavyPaths.set(pathPos[s], x);
        } else if (typ == 2){
            int u, v; cin >> u >> v;
 
            int L = LCA(u,v);
            cout << max(maxUpPath(L, u), maxUpPath(L, v)) << ' ';
        }
    }
    cout << '\n';
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    solve();
    return 0;
}