HK: Heavy Light White Falcon ( HLD )

HK: Heavy Light White Falcon ( HLD )
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     100005
#define inf    2000000000
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int nd[MX * 4 + 5];
vector<int>G[MX];
int n, cn, ptr, T[MX], L[MX], SS[MX], SC[MX], Chd[MX], Cid[MX], Cpos[MX];

void Ins(int id,int l,int r,int p,int v) {
    if(l==r) {
        nd[id]=v;
        return;
    }
    int lft=(id<<1),rgt=lft+1,md=(l+r)>>1;
    if( p<=md ) Ins(lft,l,md,p,v);
    else Ins(rgt,md+1,r,p,v);
    nd[id]=max(nd[lft],nd[rgt]);
}

int Qry(int id,int l,int r,int q1,int q2) {
    if( l==q1 && r==q2 ) return nd[id];
    int lft=(id<<1),rgt=lft+1,md=(l+r)>>1;
    if( q2<=md ) return Qry(lft,l,md,q1,q2);
    else if(q1>md ) return Qry(rgt,md+1,r,q1,q2);
    else return max(Qry(lft,l,md,q1,md),Qry(rgt,md+1,r,md+1,q2));
}

void DFS(int u, int p, int lv) {
    T[u] = p;
    L[u] = lv;
    SS[u] = 1;
    SC[u] = -1; ///spcl child
    int sz = SZ(G[u]), mx = -1;
    for(int i = 0; i < sz; i++) {
        int v = G[u][i];
        if(v == p) continue;
        DFS(v, u, lv + 1);
        SS[u] += SS[v];
        if(SS[v] > mx) {
            mx = SS[v];
            SC[u] = v;
        }
    }
}

void HLD(int u) {
    if( Chd[cn] == -1 ) Chd[cn] = u;
    Cid[u] = cn;
    Cpos[u] = ++ptr;
    if(SC[u] == -1)return;
    HLD(SC[u]);
    int sz = SZ(G[u]);
    for(int i = 0; i < sz; i++) {
        int v = G[u][i];
        if(v == SC[u] || v == T[u])continue;
        cn++;
        HLD(v);
    }
}

int LCA(int u, int v) {
    int uhead, vhead, uchain, vchain;
    while(true) {
        uchain = Cid[u];
        vchain = Cid[v];
        uhead  = Chd[uchain];
        vhead  = Chd[vchain];
        if(uchain == vchain)return (L[u] < L[v] ? u : v);
        if(L[uhead] < L[vhead]) v = T[vhead];
        else u = T[uhead];
    }
}

int rangeMax(int x, int y) {
    if(x > y) swap(x, y);
    int ret = Qry(1, 1, ptr, x, y);
    return ret;
}

int query_up_mx(int u, int p) {
    int uchain, pchain = Cid[p], ret = 0;
    int uhead;
    while(true) {
        uchain = Cid[u];
        if(uchain == pchain) {/// Take care of inclusion of LCA here
            ret = max(ret, rangeMax(Cpos[p], Cpos[u]));
            break;
        }
        uhead = Chd[uchain];
        ret = max(ret, rangeMax( Cpos[uhead] , Cpos[u] ));
        u = T[uhead];
    }
    return ret;
}

void init() {
    fr(i, 0, n) {
        G[i].clear();/// Graph vector
        Chd[i] = -1;/// chain's head
        Cid[i] = -1;/// chain's id
        Cpos[i] = 0; /// position of node in chain
        SS[i] = 0; ///Subtree size
    }
    cn = 1; /// chain no
    ptr = 0; /// total nos of chains
}

int main() {
    int tc,cs=1,i,j,k,q,x,y,z,op;
    S2(n,q);
    init();
    fr(i, 1, n - 1) {
        S2(x, y);
        x++,y++;
        G[x].pb(y);
        G[y].pb(x);
    }
    DFS(1, -1, 1);
    HLD(1);
    while(q--) {
        S(op);
        S2(x, y);
        if( op==1 ) {///Assign value to node x;
            x++;
            Ins(1,1,ptr,Cpos[x],y );
        } else { ///Find max between x to y;
            x++,y++;
            int lc = LCA(x, y);
            int mx=query_up_mx(x,lc);
            mx=max(mx,query_up_mx(y,lc));
            printf("%d\n",mx);
        }
    }
    return 0;
}