#include using namespace std; class HeavyLightDecomposition{ protected: int V; vector> G; vector stsize, parent, pathtop, depth, in, reverse_in, out; int root; private: // Subtree Size void buildStsize(int curr, int prev){ stsize[curr] = 1, parent[curr] = prev; for(int &v : G[curr]){ if(v == prev){ if(v == G[curr].back()) break; else swap(v, G[curr].back()); } buildStsize(v, curr); stsize[curr] += stsize[v]; if(stsize[v] > stsize[G[curr][0]]){ swap(v, G[curr][0]); } } } void buildPath(int curr, int prev, int &t){ in[curr] = t++; reverse_in[in[curr]] = curr; for(int v : G[curr]){ if(v == prev) continue; if(v == G[curr][0]){ pathtop[v] = pathtop[curr]; } else{ pathtop[v] = v; } depth[v] = depth[curr] + 1; buildPath(v, curr, t); } out[curr] = t; } public: HeavyLightDecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1), pathtop(V, -1), depth(V, 0), in(V, -1), reverse_in(V, -1), out(V, -1){} void add_edge(int u, int v){ G[u].push_back(v); G[v].push_back(u); } void build(int _root = 0){ root = _root; int t = 0; buildStsize(root, -1); pathtop[root] = root; buildPath(root, -1, t); } inline int get(int a){ return in[a]; } int la(int a, int k) { while(true){ int u = pathtop[a]; if(in[a] - k >= in[u]) return reverse_in[in[a] - k]; k -= in[a] - in[u] + 1; a = parent[u]; } } int lca(int a, int b){ int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ a = parent[pa], pa = pathtop[a]; } else{ b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); return a; } int dist(int a, int b){ return depth[a] + depth[b] - 2 * depth[lca(a, b)]; } int jump(int from, int to, int k) { if(!k) return from; int l = lca(from, to); int d = dist(from, to); if(d < k) return -1; if(depth[from] - depth[l] >= k) return la(from, k); k -= depth[from] - depth[l]; return la(to, depth[to] - depth[l] - k); } void subtree_query(int a, const function &func){ func(in[a], out[a]); } void path_query(int a, int b, const function &func, bool include_root = true, bool reverse_path = false){ vector> path; int pa = pathtop[a], pb = pathtop[b]; while(pathtop[a] != pathtop[b]){ if(in[pa] > in[pb]){ path.emplace_back(in[pa], in[a] + 1); a = parent[pa], pa = pathtop[a]; } else{ path.emplace_back(in[pb], in[b] + 1); b = parent[pb], pb = pathtop[b]; } } if(in[a] > in[b]) swap(a, b); if(include_root) path.emplace_back(in[a], in[b] + 1); else path.emplace_back(in[a] + 1, in[b] + 1); if(!reverse_path) reverse(path.begin(), path.end()); else for(auto &p : path) p = make_pair(V - p.second, V - p.first); for(auto [u, v] : path){ func(u, v); } } void path_noncommutative_query(int a, int b, const function &func, const function &func2){ int l = lca(a, b); path_query(a, l, func2, false, true); path_query(l, b, func, true, false); } }; template struct SegmentTreeBeats{ int n, n0; vector max_v, smax_v, max_c; vector min_v, smin_v, min_c; vector sum; vector len, ladd, lval; void update_node_max(int k, T x) { sum[k] += (x - max_v[k]) * max_c[k]; if(max_v[k] == min_v[k]){ max_v[k] = min_v[k] = x; }else if(max_v[k] == smin_v[k]){ max_v[k] = smin_v[k] = x; }else{ max_v[k] = x; } if(lval[k] != INF && x < lval[k]){ lval[k] = x; } } void update_node_min(int k, T x) { sum[k] += (x - min_v[k]) * min_c[k]; if(max_v[k] == min_v[k]){ max_v[k] = min_v[k] = x; }else if(smax_v[k] == min_v[k]){ min_v[k] = smax_v[k] = x; }else{ min_v[k] = x; } if(lval[k] != INF && lval[k] < x){ lval[k] = x; } } void push(int k){ if(n0 - 1 <= k) return; if(lval[k] != INF){ updateall(2 * k + 1, lval[k]); updateall(2 * k + 2, lval[k]); lval[k] = INF; return; } if(ladd[k] != 0){ addall(2 * k + 1, ladd[k]); addall(2 * k + 2, ladd[k]); ladd[k] = 0; } if(max_v[k] < max_v[2 * k + 1]){ update_node_max(2 * k + 1, max_v[k]); } if(min_v[2 * k + 1] < min_v[k]){ update_node_min(2 * k + 1, min_v[k]); } if(max_v[k] < max_v[2 * k + 2]){ update_node_max(2 * k + 2, max_v[k]); } if(min_v[2 * k + 2] < min_v[k]){ update_node_min(2 * k + 2, min_v[k]); } } void update(int k){ sum[k] = sum[2 * k + 1] + sum[2 * k + 2]; if(max_v[2 * k + 1] < max_v[2 * k + 2]){ max_v[k] = max_v[2 * k + 2]; max_c[k] = max_c[2 * k + 2]; smax_v[k] = max(max_v[2 * k + 1], smax_v[2 * k + 2]); }else if(max_v[2 * k + 1] > max_v[2 * k + 2]){ max_v[k] = max_v[2 * k + 1]; max_c[k] = max_c[2 * k + 1]; smax_v[k] = max(smax_v[2 * k + 1], max_v[2 * k + 2]); }else{ max_v[k] = max_v[2 * k + 1]; max_c[k] = max_c[2 * k + 1] + max_c[2 * k + 2]; smax_v[k] = max(smax_v[2 * k + 1], smax_v[2 * k + 2]); } if(min_v[2 * k + 1] < min_v[2 * k + 2]){ min_v[k] = min_v[2 * k + 1]; min_c[k] = min_c[2 * k + 1]; smin_v[k] = min(smin_v[2 * k + 1], min_v[2 * k + 2]); }else if(min_v[2 * k + 1] > min_v[2 * k + 2]){ min_v[k] = min_v[2 * k + 2]; min_c[k] = min_c[2 * k + 2]; smin_v[k] = min(min_v[2 * k + 1], smin_v[2 * k + 2]); }else{ min_v[k] = min_v[2 * k + 1]; min_c[k] = min_c[2 * k + 1] + min_c[2 * k + 2]; smin_v[k] = min(smin_v[2 * k + 1], smin_v[2 * k + 2]); } } void _query_chmin(T x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || max_v[k] <= x){ return; } if(a <= l && r <= b && smax_v[k] < x){ update_node_max(k, x); return; } push(k); _query_chmin(x, a, b, 2 * k + 1, l, (l + r) / 2); _query_chmin(x, a, b, 2 * k + 2, (l + r) / 2, r); update(k); } void _query_chmax(T x, int a, int b, int k, int l, int r) { if(b <= l || r <= a || x <= min_v[k]){ return; } if(a <= l && r <= b && x < smin_v[k]){ update_node_min(k, x); return; } push(k); _query_chmax(x, a, b, 2 * k + 1, l, (l + r) / 2); _query_chmax(x, a, b, 2 * k + 2, (l + r) / 2, r); update(k); } void addall(int k, T x) { max_v[k] += x; if(smax_v[k] != -INF) smax_v[k] += x; min_v[k] += x; if(smin_v[k] != INF) smin_v[k] += x; sum[k] += len[k] * x; if(lval[k] != INF){ lval[k] += x; }else{ ladd[k] += x; } } void updateall(int k, T x) { max_v[k] = x; smax_v[k] = -INF; min_v[k] = x; smin_v[k] = INF; max_c[k] = min_c[k] = len[k]; sum[k] = x * len[k]; lval[k] = x; ladd[k] = 0; } void _query_add(T x, int a, int b, int k, int l, int r) { if(b <= l || r <= a){ return; } if(a <= l && r <= b){ addall(k, x); return; } push(k); _query_add(x, a, b, 2 * k + 1, l, (l + r) / 2); _query_add(x, a, b, 2 * k + 2, (l + r) / 2, r); update(k); } void _query_update(T x, int a, int b, int k, int l, int r) { if(b <= l || r <= a){ return; } if(a <= l && r <= b){ updateall(k, x); return; } push(k); _query_update(x, a, b, 2 * k + 1, l, (l + r) / 2); _query_update(x, a, b, 2 * k + 2, (l + r) / 2, r); update(k); } T _query_max(int a, int b, int k, int l, int r) { if(b <= l || r <= a){ return -INF; } if(a <= l && r <= b){ return max_v[k]; } push(k); T lv = _query_max(a, b, 2 * k + 1, l, (l + r) / 2); T rv = _query_max(a, b, 2 * k + 2, (l + r) / 2, r); return max(lv, rv); } T _query_min(int a, int b, int k, int l, int r) { if(b <= l || r <= a){ return INF; } if(a <= l && r <= b){ return min_v[k]; } push(k); T lv = _query_min(a, b, 2 * k + 1, l, (l + r) / 2); T rv = _query_min(a, b, 2 * k + 2, (l + r) / 2, r); return min(lv, rv); } T _query_sum(int a, int b, int k, int l, int r) { if(b <= l || r <= a){ return 0; } if(a <= l && r <= b){ return sum[k]; } push(k); T lv = _query_sum(a, b, 2 * k + 1, l, (l + r) / 2); T rv = _query_sum(a, b, 2 * k + 2, (l + r) / 2, r); return lv + rv; } public: SegmentTreeBeats(int n) : n(n){ vector a; init(n, a); } SegmentTreeBeats(int n, vector &a) : n(n){ init(n, a); } void init(int n, vector &a){ max_v.assign(4 * n, 0), smax_v.assign(4 * n, 0), max_c.assign(4 * n, 0); min_v.assign(4 * n, 0), smin_v.assign(4 * n, 0), min_c.assign(4 * n, 0); sum.assign(4 * n, 0); len.assign(4 * n, 0), ladd.assign(4 * n, 0); lval.assign(4 * n, 0); n0 = 1; while(n0 < n) n0 <<= 1; for(int i = 0; i < 2 * n0; ++i) ladd[i] = 0, lval[i] = INF; len[0] = n0; for(int i = 0; i < n0 - 1; ++i) len[2 * i + 1] = len[2 * i + 2] = (len[i] >> 1); for(int i = 0; i < n; ++i){ max_v[n0 - 1 + i] = min_v[n0 - 1 + i] = sum[n0 - 1 + i] = (!a.empty() ? a[i] : 0); smax_v[n0 - 1 + i] = -INF; smin_v[n0 - 1 + i] = INF; max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 1; } for(int i = n; i < n0; ++i){ max_v[n0 - 1 + i] = smax_v[n0 - 1 + i] = -INF; min_v[n0 - 1 + i] = smin_v[n0 - 1 + i] = INF; max_c[n0 - 1 + i] = min_c[n0 - 1 + i] = 0; } for(int i = n0 - 2; i >= 0; --i){ update(i); } } // range minimize query void query_chmin(int a, int b, T x){ _query_chmin(x, a, b, 0, 0, n0); } // range maximize query void query_chmax(int a, int b, T x){ _query_chmax(x, a, b, 0, 0, n0); } // range add query void query_add(int a, int b, T x){ _query_add(x, a, b, 0, 0, n0); } // range update query void query_update(int a, int b, T x){ _query_update(x, a, b, 0, 0, n0); } // range minimum query T query_max(int a, int b){ return _query_max(a, b, 0, 0, n0); } // range maximum query T query_min(int a, int b){ return _query_min(a, b, 0, 0, n0); } // range sum query T query_sum(int a, int b){ return _query_sum(a, b, 0, 0, n0); } T get(int x){ return _query_sum(x, x + 1, 0, 0, n0); } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; HeavyLightDecomposition G(n); vector u(n - 1), v(n - 1), w(n - 1); for(int i = 0; i < n - 1; i++){ cin >> u[i] >> v[i] >> w[i]; G.add_edge(u[i], v[i]); } G.build(); SegmentTreeBeats seg(n); for(int i = 0; i < n - 1; i++){ int idx = max(G.get(u[i]), G.get(v[i])); seg.query_update(idx, idx + 1, w[i]); } long long ans = 0; long long x; auto query1 = [&](int l, int r){ seg.query_add(l + 1, r, x); }; auto query2 = [&](int l, int r){ ans += seg.query_sum(l, r); }; int q; cin >> q; while(q--){ int t; cin >> t; if(t == 1){ int a; cin >> a >> x; G.subtree_query(a, query1); }else{ int b; cin >> b; ans = 0; G.path_query(0, b, query2, false, false); cout << ans << "\n"; } } }