HAKER-RANK :Lazy White Falcon (DS)

HR:Lazy White Falcon (DS)

///==================================================///
///                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     200005
#define inf    2000000000
#define MD     1000000007LL
#define eps    1e-9
///===============================///

vector<int>G[MX+2];
int tmm,P[MX][20],L[MX],St[MX],Ed[MX],val[MX];

int BIT[MX+2];
void add(int p,int v) {
    for(int i=p; i<=MX; i+=i&-i)BIT[i]+=v;
}

int read(int p) {
    int ret=0;
    for(int i=p; i>0; i-=i&-i)ret+=BIT[i];
    return ret;
}

void Dfs(int u,int p,int l) {
    P[u][0]=p;
    L[u]=l;
    St[u]=++tmm;
    for(int i=0; i<SZ(G[u]); i++) {
        int v=G[u][i];
        if(v==p)continue;
        Dfs(v,u,l+1);
    }
    Ed[u]=++tmm;
}

void Par_Sparse(int n) {
    for(int j=1; j<=18; j++) {
        for(int i=1; i<=n; i++) {
            if( P[i][j-1]==-1 ) continue;
            P[i][j]=P[ P[i][j-1] ][ j-1 ];
        }
    }
}

int Kth(int x,int k) {
    int j=0;
    while(k) {
        if(k%2==1)x=P[x][j];
        k/=2,j++;
    }
    return x;
}

int Lca(int x,int y) {
    if( L[x]<L[y] ) swap(x,y);
    x=Kth(x, L[x]-L[y] );
    if( x==y ) return x;
    for(int i=18; i>=0; i--) {
        if( P[x][i]!=P[y][i]) {
            x=P[x][i],y=P[y][i];
        }
    }
    return P[x][0];
}

int main() {
    int n,q,i,j,k,x,y,op;
    S2(n,q);
    fr(i,1,n-1) {
        S2(x,y);
        x++,y++;
        G[x].pb( y );
        G[y].pb( x );
    }
    SET(P);
    tmm=0;
    Dfs(1,-1,1);
    Par_Sparse(n);
    while(q--) {
        S(op);
        S2(x,y);
        x++;
        if(op==1) { ///assign x to y;
            add( St[x],-val[x]+y );
            add( Ed[x], val[x]-y );
            val[x]=y;
        } else { ///find sum from x to y;
            y++;
            int lc=Lca(x,y);
            int dis=read(St[x])+read(St[y])-2*read(St[lc]);
            printf("%d\n",dis+val[lc]);
        }
    }
    return 0;
}