CCCPaste

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;
}