Revise paste TeraData_OA_4

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

/**
 * Segment Tree supporting:
 * - Range increment updates
 * - Point queries
 */
class SegmentTree {
    vector<long long> tree, lazy;
    int size;

public:
    explicit SegmentTree(int n) : size(n) {
        tree.assign(4 * n + 5, 0);
        lazy.assign(4 * n + 5, 0);
    }

// Build the tree from a given array
    void build(int idx, int left, int right, const vector<long long>& values) {
        if (left == right) {
            tree[idx] = values[left];
            return;
        }
        int mid = (left + right) / 2;
        build(idx * 2, left, mid, values);
        build(idx * 2 + 1, mid + 1, right, values);
    }

// Lazy range update
    void update(int idx, int ql, int qr, int left, int right, long long val) {
        if (qr < left || ql > right) return;
        if (ql <= left && right <= qr) {
            lazy[idx] += val;
            return;
        }
        int mid = (left + right) / 2;
        update(idx * 2, ql, qr, left, mid, val);
        update(idx * 2 + 1, ql, qr, mid + 1, right, val);
    }

// Point query: propagate laziness as we go down
    long long query(int idx, int pos, int left, int right) {
        if (pos < left || pos > right) return 0;
        if (left == right) {
            tree[idx] += lazy[idx];
            lazy[idx] = 0;
            return tree[idx];
        }

// push lazy value to children
        lazy[idx * 2] += lazy[idx];
        lazy[idx * 2 + 1] += lazy[idx];
        lazy[idx] = 0;

int mid = (left + right) / 2;
        if (pos <= mid) return query(idx * 2, pos, left, mid);
        else return query(idx * 2 + 1, pos, mid + 1, right);
    }
};

// Global timer for Euler tour
int timer = 1;

/**
 * DFS to compute:
 * - timeIn/timeOut for each node
 * - prefix sum (sumToRoot)
 * - binary lifting table
 */
void dfs(int node, int parent,
         const vector<vector<pair<int, int>>>& graph,
         vector<int>& timeIn, vector<int>& timeOut,
         vector<long long>& sumToRoot,
         vector<vector<int>>& up) {
    
    timeIn[node] = timer++;

for (auto [child, weight] : graph[node]) {
        if (child == parent) continue;
        up[child][0] = node;
        sumToRoot[child] = sumToRoot[node] + weight;
        dfs(child, node, graph, timeIn, timeOut, sumToRoot, up);
    }

timeOut[node] = timer;
}

/** Checks if 'a' is an ancestor of 'b' */
bool isAncestor(int a, int b, const vector<int>& timeIn, const vector<int>& timeOut) {
    return timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b];
}

/** Compute Lowest Common Ancestor (LCA) using binary lifting */
int findLCA(int u, int v, const vector<vector<int>>& up,
            const vector<int>& timeIn, const vector<int>& timeOut) {

if (isAncestor(u, v, timeIn, timeOut)) return u;
    if (isAncestor(v, u, timeIn, timeOut)) return v;

for (int i = 24; i >= 0; --i) {
        int ancestor = up[u][i];
        if (ancestor && !isAncestor(ancestor, v, timeIn, timeOut)) {
            u = ancestor;
        }
    }
    return up[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

int n;
    cin >> n;

vector<vector<pair<int, int>>> graph(n + 1);
    vector<int> from(n), to(n), weight(n);

// Input edges
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        from[i] = u;
        to[i] = v;
        weight[i] = w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

vector<int> timeIn(n + 1), timeOut(n + 1);
    vector<long long> sumToRoot(n + 1, 0);
    vector<vector<int>> up(n + 1, vector<int>(25, 0));

// Run DFS from root (1)
    dfs(1, 0, graph, timeIn, timeOut, sumToRoot, up);

// Build binary lifting table
    for (int j = 1; j < 25; j++) {
        for (int i = 1; i <= n; i++) {
            int parent = up[i][j - 1];
            up[i][j] = parent ? up[parent][j - 1] : 0;
        }
    }

// Align edges so "from" is always parent and "to" is child
    for (int i = 1; i < n; i++) {
        if (timeIn[from[i]] > timeIn[to[i]]) swap(from[i], to[i]);
    }

// Prepare array for segment tree using DFS order
    vector<long long> dfsArray(n + 1, 0);
    for (int i = 1; i <= n; i++) dfsArray[timeIn[i]] = sumToRoot[i];

SegmentTree seg(n + 1);
    seg.build(1, 0, n, dfsArray);

int q;
    cin >> q;

while (q--) {
        int type;
        cin >> type;

if (type == 1) {
            // Update edge weight
            int edgeIdx, newWeight;
            cin >> edgeIdx >> newWeight;

int u = from[edgeIdx];
            int v = to[edgeIdx];
            long long delta = newWeight - weight[edgeIdx];
            weight[edgeIdx] = newWeight;

int l = timeIn[v], r = timeOut[v] - 1;
            if (l <= r) seg.update(1, l, r, 0, n, delta);

} else if (type == 2) {
            // Query distance between two nodes
            int u, v;
            cin >> u >> v;

long long distU = seg.query(1, timeIn[u], 0, n);
            long long distV = seg.query(1, timeIn[v], 0, n);

if (isAncestor(u, v, timeIn, timeOut) || isAncestor(v, u, timeIn, timeOut)) {
                cout << llabs(distU - distV) << '\n';
            } else {
                int lca = findLCA(u, v, up, timeIn, timeOut);
                long long distLCA = seg.query(1, timeIn[lca], 0, n);
                cout << llabs(distU + distV - 2 * distLCA) << '\n';
            }
        }
    }

return 0;
}