// - Author: Jorge_Slime - 11.01.2026 | 00:55:18 #include using namespace std; #define forn(i,a,b) for(auto i{a};i<(b);++i) #define all(x) (x).begin(),(x).end() #define sz(x) int((x).size()) #if defined(SLIME) #include "/home/jorge/slime_debug.hpp" #else #define _(...) void(77) #endif using i64 = int64_t; struct Node{ i64 sum; i64 lazyVal; bool haslazy; }; class Lazy_SegTree{ public: #define left node << 1 #define right node<< 1 | 1 const i64 NEUTRO = 0; std::vector tree; int size, logv = 0; Lazy_SegTree() : size(0), logv(0) {} Lazy_SegTree(int n){ init(n); } void init(int n){ logv = 0; size = n; while((1< &ar) { int tam = (int)ar.size(); for (int i = 0; i < tam; i++) { tree[size + i] = {ar[i],0,false}; } for (int i = size - 1; i ; --i) { modify(i); } } void apply(int node, int l, int r, i64 val){ tree[node].sum += val * (r - l + 1); // asignación tree[node].lazyVal += val; tree[node].haslazy = true; } void propagate(int node, int l ,int r){ if(tree[node].haslazy){ int mid = (l + r) >> 1; apply(left, l, mid, tree[node].lazyVal); apply(right, mid + 1, r, tree[node].lazyVal); tree[node].haslazy = false; tree[node].lazyVal = 0; } } void upd(int node,int nl,int nr,int ql,int qr,i64 val){ if(nr < ql || nl > qr) return; if(ql <= nl && nr <= qr){ apply(node,nl,nr,val); return; } propagate(node,nl,nr); int mid = (nl + nr) >> 1; upd(left, nl, mid, ql, qr, val); upd(right, mid + 1,nr, ql ,qr, val); modify(node); } void update(int l ,int r , i64 val){ if(l>r) return; upd(1,0,size-1,l,r,val); } i64 queryRec(int node, int nl ,int nr, int ql, int qr){ if(nr < ql || nl > qr) return NEUTRO; if(ql <= nl && nr <= qr){ return tree[node].sum; } propagate(node, nl ,nr); int mid = (nl + nr)>>1; i64 iz = queryRec(left, nl , mid,ql,qr); i64 de = queryRec(right , mid + 1, nr, ql,qr); return op(iz,de); } i64 query(int l ,int r){ if(l>r) return NEUTRO; return queryRec(1, 0 ,size-1,l,r); } static constexpr i64 op(i64 a, i64 b){ return a + b; } #undef left #undef right }; template//if edges weights struct HLD{ int n, times; vector> G; vector sz,in,head,fa,depth,heavy,rev_in; HLD(int n_){ init(n_); } void init(int n_){ n = n_;times = 0;G.assign(n,{}); fa.assign(n, -1); depth.assign(n, 0); head.assign(n, -1);in.assign(n, 0); sz.assign(n, 0);heavy.assign(n,-1); rev_in.assign(n,0); } void build(int root){ dfsSz(root); dfsHLD(root, root); } void add_edge(int u, int v) { G[u].emplace_back(v); G[v].emplace_back(u); } // LCA utils bool is_ancestor(int a, int b) const { return in[a] <= in[b] && in[b] < in[a] + sz[a]; } int lca(int u,int v){ while(head[u] != head[v]){ if(depth[head[u]] < depth[head[v]]) std::swap(u,v); u = fa[head[u]]; } return depth[u] < depth[v] ? u : v; } int dist(int u,int v){ return depth[u] + depth[v] - 2 * depth[lca(u,v)]; } int get_kth_ancestor(int a, int k){ while (a != -1) { int h = head[a]; if (in[a] - in[h] >= k) return rev_in[in[a] - k]; k -= in[a] - in[h] + 1; a = fa[h]; } return -1; } int get_kth_node_on_path(int a, int b, int k){ int anc = lca(a, b); k--; int d1 = depth[a] - depth[anc]; int d2 = depth[b] - depth[anc]; if (k <= d1) return get_kth_ancestor(a, k); else return get_kth_ancestor(b, d1 + d2 - k); } // Update and Queries void updateNode(int node, i64 v, auto& seg) { seg.update(in[node],in[node],v); } i64 queryNode(int node,auto& seg){ return seg.query(in[node],in[node]); } void updateSubtree(int node,i64 v, auto& seg){ seg.update(in[node] + P,in[node] + sz[node] - 1,v); } i64 querySubtree(int node,auto& seg){ return seg.query(in[node] + P,in[node] + sz[node] - 1); } void updatePath(int a,int b,i64 v, auto& seg){ while (head[a] != head[b]) { if (depth[head[a]] > depth[head[b]]) { seg.update(in[head[a]], in[a],v); a = fa[head[a]]; } else { seg.update(in[head[b]], in[b],v); b = fa[head[b]]; } } if (depth[a] > depth[b]) std::swap(a, b); seg.update(in[a] + P, in[b], v); } i64 queryPath(int a, int b, auto& seg) { i64 ra = seg.NEUTRO, rb = seg.NEUTRO; while (head[a] != head[b]) { if (depth[head[a]] > depth[head[b]]) { ra = seg.op(ra, seg.query(in[head[a]], in[a])); a = fa[head[a]]; } else { rb = seg.op(rb, seg.query(in[head[b]], in[b])); b = fa[head[b]]; } } if (depth[a] > depth[b]) std::swap(a, b); return seg.op(ra,seg.op(seg.query(in[a] + P, in[b]),rb)); } void initWeights(auto& e,auto& seg){ forn(i, 0, n - 1){ auto [u,v,w] = e[i]; int nodo=(depth[u]>depth[v]?u:v); updateNode(nodo, w, seg); } } private: void dfsSz(int node){ sz[node] = 1; int mx = 0; for(auto& child : G[node]){ if(child == fa[node]) continue; fa[child] = node; depth[child] = depth[node] + 1; dfsSz(child); sz[node] += sz[child]; if(sz[child] > mx){ mx = sz[child]; heavy[node] = child; } } } void dfsHLD(int node,int h){ in[node] = times++; head[node] = h; rev_in[in[node]] = node; if(heavy[node] != -1) dfsHLD(heavy[node], h); for(auto& child : G[node]){ if(child == fa[node] || child == heavy[node]) continue; dfsHLD(child , child); } } }; struct EdgeNode{ int u,v; i64 w; }; auto solve([[maybe_unused]]auto&& tc)->void{ int n; cin >> n; vector edges(n - 1); Lazy_SegTree seg(n); HLD<1> hld(n); forn(i,0,n - 1){ int u,v; i64 w; cin >> u >> v >>w; hld.add_edge(u, v); edges[i] = {u,v,w}; } hld.build(0); hld.initWeights(edges,seg); int q; cin >> q; forn(i, 0, q){ int t; cin >> t; if(t == 2){ int b; cin >> b; i64 ans = hld.queryPath(0,b,seg); cout << ans << '\n'; }else{ int a; i64 x; cin >> a >> x; hld.updateSubtree(a, x, seg); } } }; [[gnu::target("avx2")]] auto main(void) -> int { cin.tie(nullptr)->sync_with_stdio(false); cin.exceptions(ios::failbit | ios::badbit); size_t t_c = 1; //cin >> t_c; forn(t,0,t_c){ _(case(t)); solve(t); } _(time_()); return 0; } // I can....