data-structure - Heavy - light (1348 - Aladdin and the Return Journey)

#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */

#define Long                    long long
#define Ulong                   unsigned long long
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define pb(a)                   push_back((a))
#define all(x)                  (x).begin(),(x).end()
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define Di(x)                   int x;scanf("%d",&x)
#define min(a,b)                ((a)>(b) ? (b) : (a) )
#define max(a,b)                ((a)>(b) ? (a):(b))
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 3e4+4 , LG = 20;
int n;
int P[N][20], lev[N], ch = 0;
int chainNo[N], head[N], subsize[N], child[N], pos[N];
int Ar[N], tot = 0 , value[N];

vector<int> G[N];



int seg[N*4];
void build(int n,int b,int e)
{
    if(b==e) {
        seg[n] = Ar[b];return;
    }
    int mid= (b+e)/2;
    build(lc,b,mid);
    build(rc, mid+1,e);
    seg[n] = seg[lc] + seg[rc];
}
void update(int n,int b,int e,int pos,int v)
{
    if(b==e && b== pos) {
        seg[n] = v;
        return ;
    }
    int mid = (b+e)/2;
    if(pos <= mid ) update(lc,b,mid,pos,v);
    else update(rc,mid+1,e,pos,v);
    seg[n] = seg[lc] + seg[rc];
}

int query(int n,int b,int e,int i,int j)
{
    if(b>j||e<i) return 0;
    if(b>=i && e <= j ) {
        return seg[n];
    }
    int mid = (b+e)/2;
    return query(lc,b,mid,i,j) + query(rc,mid+1,e,i,j);
}
/********** MAIN HLD-PART **********************/
void dfs(int u,int p)
{
    subsize[u] = 1;
    for(int i = 0; i < G[u].size(); i ++ ) {
        int v = G[u][i];
        if(v == p ) continue;
        lev[v] = 1  + lev[u];
        P[v][0] = u; // Modify
        dfs(v,u);

        subsize[u] += subsize[v];
        if(child[u] == -1 || subsize[v] > subsize[child[u]] ) {
            child[u] = v;
        }

    }
}
void HLD(int u,int p)
{
    if(head[ch] == -1) head[ch] = u;
    Ar[ ++tot ] = value[u];
    pos[u] = tot;
    chainNo[u] = ch;

    if(child[u]  > 0 ) HLD(child[u], u );
    for(int i = 0; i < G[u].size(); i ++ ) {
        int v = G[u][i];
        if(v == p || v == child[u]) continue;
        ++ch;
        HLD(v,u);
    }
}

int LCA(int u,int v)
{
    if(lev[u] > lev[v]) swap(u,v);
    int d = lev[v] - lev[u];
    for(int i = LG - 1; i >= 0 ;  i -- ) {
        if( d  &1<<i){
            v = P[v][i];
        }
    }

    if(u==v) return u;
    for(int i = LG-1; i >= 0 ; i -- ) {
        if(P[u][i] != P[v][i]) {
            u = P[u][i];
            v = P[v][i];
        }
    }
    return P[v][0];
}

int queryUp(int from, int to) // Climb up to
{
    int ret = 0;
    while(chainNo[from ] != chainNo[to] ) {
        int h = head[chainNo[from]];
        ret += query(1,1,tot, pos[h], pos[from]); // Modify
        from = P[h][0];
    }
    ret += query(1,1,tot,pos[to], pos[from]); // Modify
    return ret;
}
void process()
{
    memset(P,-1,sizeof(P));
    memset(head,-1,sizeof(head));
    memset(child,-1,sizeof(child));

    tot = 0 , ch = 0;
    dfs(1,-1);
    HLD(1,-1);
    build(1,1,tot);
    for(int i = 1; i < LG; i ++ ) {
        for(int j = 1; j <= n; j ++ ) if(P[j][i-1] !=-1 ) P[j][i] = P[P[j][i-1]][i-1];
    }
}
/************************** END ************************/
int main()
{
    //freopen("in.txt","r",stdin);
    int t,cs=  0;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);

        for(int i= 1;i <= n; i ++) scanf("%d",&value[i]);
        for(int i = 1; i <= n-1; i ++ ) {
            int a,b;
            scanf("%d %d",&a,&b);
            a++,b++;
            G[a].pb(b);
            G[b].pb(a);
        }
        process();
        int q;
        scanf("%d",&q);
        printf("Case %d:\n", ++cs);
        while(q--){
            int type;
            scanf("%d",&type);
            if(type == 0) {
                int a,b;
                scanf("%d %d",&a,&b);
                a++,b++;
                int k = LCA(a,b);
                printf("%d\n", queryUp(a,k) + queryUp(b,k) - value[k]); // Climbing Up
            }
            else {
                int a,b;
                scanf("%d %d",&a,&b); a ++;
                value[a]  = b;
                update(1,1,tot,pos[a],b);
            }
        }
        for(int i = 1;i <= n; i ++ ) G[i].clear();
    }
    return 0;
}