Heavy Light Composition

#include <bits/stdc++.h>
#ifdef TEST
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define X first
#define Y second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
#define MXV 100000
#define LOW(x) (x&(-(x)))
struct BIT{
    vector<ll> orig;
    vector<ll> arr;
    BIT(){
        orig.EB(0); // placeholder
    }
    void construct(){
        arr.resize(orig.size());
        for(int i = 1 ; i < int(orig.size()) ; ++i){
            add(i, orig[i]);
        }
    }
    void add(int i, int v){
        for(;i<=int(size());i+=LOW(i)) arr[i] += v;
    }
    ll sum(int i){
        ll sum = 0;
        for(;i>0;i-=LOW(i)) sum += arr[i];
        return sum;
    }
    // [0] is not used
    size_t size(){return arr.size()-1;}
    ll sum_all(){return sum(size());}
};
// graph
map<int, int> graph[MXV+5]; // dest & weight
map<int, BIT> bit4tree;
pair<int, int> edges[MXV+5];

// Heavy Light Decomposition
int size[MXV+5], maxCh[MXV+5], depth[MXV+5], pa[MXV+5];
int chain_top[MXV+5], ord[MXV+5], chain_indx[MXV+5];
int ord_top = 0;
// HLD
void preDfs(int n, int _pa){
    size[n] = 1;
    for(auto &ch : graph[n]){
        if(ch.X != _pa){
            pa[ch.X] = n;
            depth[ch.X] = depth[n] + 1;
            preDfs(ch.X, n);
            if(maxCh[n] < 0 || size[maxCh[n]] < size[ch.X]) maxCh[n] = ch.X;
            size[n] += size[ch.X];
        }
    }
}
// n=>current node id, top => chain top node id (glob), indx => in chain (local) id
void decomp(int n, int top, int indx){
    ord[n] = ord_top++;
    chain_top[n] = top;
    chain_indx[n] = indx;
    if(maxCh[n] < 0){
        return;
    }
    bit4tree[top].orig.EB(graph[n][maxCh[n]]);
    decomp(maxCh[n], top, indx+1);
    for(auto ch : graph[n]){
        if(ch.X != maxCh[n] && ch.X != pa[n]){ // no back edge or max child edge
            decomp(ch.X, ch.X, 0);
        }
    }
}
ll LCA(int u, int v){
    ll sum = 0;
    int tu = chain_top[u], tv = chain_top[v];
    while(tu != tv){
        if(depth[tu] < depth[tv]){
            swap(tu, tv);
            swap(u, v);
        }
        sum += bit4tree[tu].sum(chain_indx[u]) + graph[tu][pa[tu]];
        debug("@@%d %d\n", bit4tree[tu].sum(chain_indx[u]), graph[tu][pa[tu]]);
        tu = chain_top[u = pa[tu]];
    }
    if(depth[u] < depth[v]) swap(u, v); // assert u deeper
    sum += bit4tree[tu].sum(chain_indx[u]) - bit4tree[tv].sum(chain_indx[v]);
    debug("@@%d %d\n", bit4tree[tu].sum(chain_indx[u]), bit4tree[tv].sum(chain_indx[v]));
    return sum;
}

void init(){
    memset(maxCh, 0xff, sizeof(maxCh));
    memset(depth, 0x00, sizeof(depth));
    memset(chain_top, 0xff, sizeof(chain_top));
    memset(ord, 0x00, sizeof(ord));
}
int main(){
    init();
    int N, cnt = 0;
    scanf("%d", &N);
    for(int i = 1 ; i < N ; ++i){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        graph[a][b] = w;
        graph[b][a] = w;
        edges[cnt++] = make_pair(a, b);
    }
    preDfs(1, -1);
    decomp(1, 1, 0);
    for(auto &v : bit4tree){
        v.Y.construct();
    }
    int Q;
    scanf("%d", &Q);
    for(int i = 0 ; i < Q ; ++i){
        int op, a, b;
        scanf("%d%d%d", &op, &a, &b);
        if(op == 1){
            int u, v;
            tie(u, v) = edges[a-1];
            int tmp = graph[u][v];
            graph[u][v] = b;
            graph[v][u] = b;
            if(chain_top[u] == chain_top[v]){
                if(depth[u] < depth[v]){
                    swap(u, v);
                }
                bit4tree[chain_top[u]].add(chain_indx[u], b-tmp);
            }
        }
        if(op == 2){
            ll ans = LCA(a, b);
            printf("%lld\n", ans);
        }
    }
    return 0;
}