// >>> TEMPLATES #include using namespace std; using ll = long long; using ld = long double; using i32 = int32_t; using i64 = int64_t; #define int ll #define double ld #define rep(i,n) for (int i = 0; i < (int)(n); i++) #define rep1(i,n) for (int i = 1; i <= (int)(n); i++) #define repR(i,n) for (int i = (int)(n)-1; i >= 0; i--) #define rep1R(i,n) for (int i = (int)(n); i >= 1; i--) #define loop(i,a,B) for (int i = a; i B; i++) #define loopR(i,a,B) for (int i = a; i B; i--) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define pb push_back #define eb emplace_back #define mp make_pair #define fst first #define snd second auto constexpr INF32 = numeric_limits::max()/2-1; auto constexpr INF64 = numeric_limits::max()/2-1; auto constexpr INF = numeric_limits::max()/2-1; #ifdef LOCAL #include "debug.hpp" #define dump(...) cerr << "[" << setw(3) << __LINE__ << ":" << __FUNCTION__ << "] ", dump_impl(#__VA_ARGS__, __VA_ARGS__) #define say(x) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] " << x << endl #define debug if (1) #else #define dump(...) (void)(0) #define say(x) (void)(0) #define debug if (0) #endif template using pque_max = priority_queue; template using pque_min = priority_queue, greater >; template ::value>::type> ostream& operator<<(ostream& os, T const& v) { bool f = true; for (auto const& x : v) os << (f ? "" : " ") << x, f = false; return os; } template ::value>::type> istream& operator>>(istream& is, T &v) { for (auto& x : v) is >> x; return is; } template istream& operator>>(istream& is, pair& p) { return is >> p.first >> p.second; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } iosetup; template struct FixPoint : private F { constexpr FixPoint(F&& f) : F(forward(f)) {} template constexpr auto operator()(T&&... x) const { return F::operator()(*this, forward(x)...); } }; struct MakeFixPoint { template constexpr auto operator|(F&& f) const { return FixPoint(forward(f)); } }; #define MFP MakeFixPoint()| #define def(name, ...) auto name = MFP [&](auto &&name, __VA_ARGS__) template struct vec_impl { using type = vector::type>; template static type make_v(size_t n, U&&... x) { return type(n, vec_impl::make_v(forward(x)...)); } }; template struct vec_impl { using type = T; static type make_v(T const& x = {}) { return x; } }; template using vec = typename vec_impl::type; template auto make_v(Args&&... args) { return vec_impl::make_v(forward(args)...); } template void quit(T const& x) { cout << x << endl; exit(0); } template constexpr bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; } template constexpr bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; } template constexpr auto sumof(It b, It e) { return accumulate(b,e,typename iterator_traits::value_type{}); } template int sz(T const& x) { return x.size(); } template int lbd(C const& v, T const& x) { return lower_bound(v.begin(), v.end(), x)-v.begin(); } template int ubd(C const& v, T const& x) { return upper_bound(v.begin(), v.end(), x)-v.begin(); } template int ppt(C const& v, F f) { return partition_point(v.begin(), v.end(), f)-v.begin(); } // <<< // >>> HLD struct HLD { vector> g; vector vid,inv,head,sz,dep,par; bool built = false; void dfs1(int x) { for (auto &y : g[x]) { if (y == par[x]) { swap(y, g[x].back()); g[x].pop_back(); break; } } for (auto &y : g[x]) { par[y] = x; dep[y] = dep[x] + 1; dfs1(y); sz[x] += sz[y]; if (sz[y] > sz[g[x][0]]) swap(y, g[x][0]); } } void dfs2(int x, int &id) { vid[x] = id++; for (auto y : g[x]) { head[y] = (y == g[x][0] ? head[x] : y); dfs2(y,id); } } HLD(int n) : g(n),vid(n),inv(n),head(n),sz(n,1),dep(n,0),par(n,-1) {} void add_edge(int x, int y) { g[x].push_back(y); g[y].push_back(x); built = false; } void build(int root = 0) { dfs1(root); head[root] = root; int id = 0; dfs2(root,id); rep (x,g.size()) inv[vid[x]] = x; built = true; } int lca(int x, int y) const { assert(built); while (1) { if (vid[x] > vid[y]) swap(x,y); if (head[x] == head[y]) return x; y = par[head[y]]; } } int dist(int x, int y) const { assert(built); return dep[x] + dep[y] - 2*dep[lca(x,y)]; } int edge_id(int x, int y) const { assert(built); if (x == par[y]) return vid[y]; if (y == par[x]) return vid[x]; return -1; } vector> path(int x, int y, bool with_lca) const { assert(built); vector> ret; while (1) { if (vid[x] > vid[y]) swap(x,y); if (head[x] == head[y]) { ret.emplace_back(vid[x] + (with_lca ? 0 : 1), vid[y]+1); return ret; } else { ret.emplace_back(vid[head[y]], vid[y]+1); y = par[head[y]]; } } } vector> vertices(int x, int y) const { return path(x,y,true); } vector> edges(int x, int y) const { return path(x,y,false); } }; // <<< // >>> lazy segment tree template struct LazySegtree : Handler { static int32_t btmbit(int64_t x) { return x ? __builtin_ctzll(x) : -1; } // static int32_t btmbit(int32_t x) { return x ? __builtin_ctz(x) : -1; } using Value = typename Handler::Value; using Lazy = typename Handler::Lazy; using Handler::unit_value; // () -> Value using Handler::unit_action; // () -> Lazy using Handler::merge; // (Value,Value) -> Value using Handler::act; // (Lazy,Lazy&,Value&) -> void vector v; vector lz; int n; mutable Lazy tmp; LazySegtree() {} template LazySegtree(T&&... x) { init(forward(x)...); } template ()(0))> void init(int n, F gen) { assert(n >= 0); this->n = n; v.resize(2*n); lz.assign(n, unit_action()); for (int i = 0; i < n; i++) v[n+i] = gen(i); for (int i = n-1; i >= 1; i--) v[i] = merge(v[2*i],v[2*i+1]); } void init(int n) { init(n, [&](int) { return unit_value(); }); } void init(int n, Value const& x) { init(n, [&](int) { return x; }); } void init(vector const& v) { init(v.size(), [&](int i) { return v[i]; }); } int size() const { return n; } void act(Lazy const& x, int i) { act(x, (i < n ? lz[i] : tmp), v[i]); } void flush(int k) { if (n <= k || lz[k] == unit_action()) return; act(lz[k], 2*k); act(lz[k], 2*k+1); lz[k] = unit_action(); } void flush(int l, int r) { for (int p = __lg(l += n), q = __lg(r += n-1); q; --p,--q) { flush(l >> p); flush(r >> q); } } void build(int i) { i += n; i >>= btmbit(i); while (i >>= 1) v[i] = merge(v[2*i],v[2*i+1]); } Value get(int l, int r) { assert(0 <= l); assert(l <= r); assert(r <= n); flush(l,r); Value x = unit_value(), y = unit_value(); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l&1) x = merge(x,v[l++]); if (r&1) y = merge(v[--r],y); } return merge(x,y); } void apply(int l, int r, Lazy const& x) { assert(0 <= l); assert(l <= r); assert(r <= n); flush(l,r); for (int a = l+n, b = r+n; a < b; a >>= 1, b >>= 1) { if (a&1) act(x, a++); if (b&1) act(x, --b); } build(l); build(r); } Value operator[](int i) const { return get(i); } Value get(int i) const { assert(0 <= i); assert(i < n); Value x = v[i += n]; while (i >>= 1) act(lz[i], tmp, x); return x; } void set(int i, Value const& x) { assert(0 <= i); assert(i < n); for (int p = __lg(i += n); p; --p) flush(i >> p); for (v[i] = x; i >>= 1; ) v[i] = merge(v[2*i],v[2*i+1]); } vector dat() const { vector ret(size()); for (int i = 0; i < size(); i++) ret[i] = get(i); return ret; } }; // <<< struct RangeSumAdd { using Value = pair; // (value, node length) using Lazy = int; constexpr static Value unit_value() { return {0,0}; } constexpr static Lazy unit_action() { return 0; } constexpr static Value merge(Value const& x, Value const& y) { return { x.fst + y.fst, x.snd + y.snd }; } static void act(Lazy x, Lazy &y, Value &z) { y += x; z.fst += x * z.snd; } }; int32_t main() { int n; cin >> n; HLD hld(n); vector> es; rep (i,n-1) { int u,v,w; cin >> u >> v >> w; hld.add_edge(u,v); es.eb(u,v,w); } hld.build(); LazySegtree seg(n); for (auto tup : es) { int u,v,w; tie(u,v,w) = tup; seg.set(hld.edge_id(u,v), mp(w,1LL)); } int q; cin >> q; rep (_,q) { int type; cin >> type; if (type == 1) { int a,x; cin >> a >> x; int l = hld.vid[a]+1, r = hld.vid[a] + hld.sz[a]; seg.apply(l,r,x); } else { int b; cin >> b; int sum = 0; for (auto p : hld.edges(0,b)) { int l,r; tie(l,r) = p; sum += seg.get(l,r).fst; } cout << sum << "\n"; } } }