// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // HLD( , root ) // === .build() === // .fold(hi, lo, func, inclusive) // where func(l, r) proceeds with [l, r) // === O(1) === // .in(a) : in-time of Euler Tour : alias = .[a] // .out(a) : out-time of Euler Tour // .rev(a) : rev[in[a]] = a // .head(a) : ascend all light edges // .tail(a) : descend all heavy edges // --- // .subtree_size(a) // .depth(a) : 0-indexed // .parent(a) : -1 if [a] is root // .heavy(a) : [a] cannot be a leaf. return the node opposite of the heavy edge // === O(log n) === // .climb(a) // .descendTo(from, to, steps) // .steps(a, b) // === --- === // for subtree : [ .in(a) , .out(a) ) // (exclusive) : [ .in_exclusive(a) , .out(a) ) // HL-Decomposition {{{ #include #include #include // based on Euler Tour struct HLD { public: using size_type = std::size_t; using graph_type = std::vector< std::vector< int > >; private: size_type n; std::vector< size_type > hd, tl; std::vector< size_type > sub; std::vector< size_type > dep; std::vector< int > par; std::vector< size_type > vid; size_type root; graph_type tree; public: HLD() : n(0) {} HLD(size_type n, size_type root = 0) : n(n), hd(n), tl(n), sub(n), dep(n), par(n), vid(n), tree(n) { setRoot(root); } HLD(const graph_type &tree, size_type root) : HLD(tree.size(), root) { this->tree = tree; } void setRoot(size_type root) { assert(root < n); this->root = root; } private: bool built = 0; std::vector< size_type > vid_rev; public: void build() { assert(!built && n); built = 1; vid_rev.resize(n); hd[root] = root; dfs0(); dfs1(); for(size_type i = 0; i < n; i++) vid_rev[vid[i]] = i; } private: void dfs0() { std::vector< int > used(n); std::vector< std::tuple< size_type, int, size_type > > stk; stk.reserve(n); stk.emplace_back(root, -1, 0); while(stk.size()) { size_type i, d; int p; std::tie(i, p, d) = stk.back(); if(!used[i]) { used[i] = 1; par[i] = p; dep[i] = d; for(auto &j : tree[i]) if(j != p) { stk.emplace_back(j, i, d + 1); } } else { stk.pop_back(); sub[i] = 1; for(auto &j : tree[i]) if(j != p) { if(sub[j] > sub[tree[i].back()]) { std::swap(tree[i].back(), j); } sub[i] += sub[j]; } if(tree[i].back() != p) { tl[i] = tl[tree[i].back()]; } else { tl[i] = i; } } } } void dfs1() { std::vector< int > used(n); std::vector< std::tuple< size_type, int > > stk; stk.reserve(n); stk.emplace_back(root, -1); size_type id = 0; while(stk.size()) { size_type i; int p; std::tie(i, p) = stk.back(), stk.pop_back(); vid[i] = id++; for(auto j : tree[i]) if(j != p) { hd[j] = j == tree[i].back() ? hd[i] : j; stk.emplace_back(j, i); } } } public: size_type operator[](size_type i) const { return in(i); } size_type in(size_type i) const { assert(built); assert(i < n); return vid[i]; } size_type in_exclusive(size_type i) const { return in(i) + 1; } size_type out(size_type i) const { assert(built); assert(i < n); return vid[i] + sub[i]; } size_type out_exclusive(size_type i) const { return out(i) - 1; } size_type head(size_type i) const { assert(built); return hd.at(i); } size_type tail(size_type i) const { assert(built); return tl.at(i); } size_type rev(size_type i) const { assert(built); return vid_rev.at(i); } size_type subtree_size(size_type i) const { assert(built); return sub.at(i); } size_type depth(size_type i) const { assert(built); return dep.at(i); } int parent(size_type i) const { assert(built); return par.at(i); } size_type steps(size_type a, size_type b) const { assert(built); assert(a < n && b < n); return dep[a] + dep[b] - 2 * dep[lca(a, b)]; } size_type climb(size_type a, long long t) const { assert(built); assert(a < n && t >= 0); while(t) { long long c = std::min< long long >(vid[a] - vid[hd[a]], t); t -= c; a = vid_rev[vid[a] - c]; if(t && a != root) { t--; a = par[a]; } if(a == root) break; } return a; } size_type descendTo(size_type from, size_type to, long long steps) const { assert(built); assert(steps >= 0); assert(from < n && to < n); return climb(to, dep[to] - dep[from] - steps); } void add_edge(size_type a, size_type b) { assert(!built); assert(a < n && b < n); tree[a].emplace_back(b); tree[b].emplace_back(a); } size_type lca(size_type a, size_type b) const { assert(built); assert(a < n && b < n); while(1) { if(vid[a] > vid[b]) std::swap(a, b); if(hd[a] == hd[b]) return a; b = par[hd[b]]; } } size_type heavy(size_type a) const { assert(built); assert(a < n); assert(tree[a].back() != par[a]); return tree[a].back(); } void fold(size_type hi, int lo, std::function< void(int, int) > f, bool inclusive) const { assert(built); assert(hi < n && 0 <= lo && lo < (int) n); while(lo != -1 && dep[lo] >= dep[hi]) { size_type nex = std::max(vid[hd[lo]], vid[hi]); f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1); lo = par[hd[lo]]; } } size_type size() const { return n; } }; // }}} const int N = 1e5; std::vector>> g; int n; // LazySegmentTree( size [, initial] ) // LazySegmentTree( ) /// --- LazySegmentTree {{{ /// #include #include #include #include template < class M_act > struct LazySegmentTree { public: using Monoid = typename M_act::Monoid; using X = typename Monoid::T; using M = typename M_act::M; private: size_t n; int h; vector< X > data; vector< M > lazy; vector< size_t > nodeLength; // call before use data[i] void eval(size_t i) { if(lazy[i] == M_act::identity()) return; data[i] = M_act::actInto(lazy[i], nodeLength[i], data[i]); if(i < n) { lazy[i * 2] = M_act::op(lazy[i], lazy[i * 2]); lazy[i * 2 + 1] = M_act::op(lazy[i], lazy[i * 2 + 1]); } lazy[i] = M_act::identity(); } // call before use seg[i] = data[i + n] void evalDown(size_t i) { i += n; for(int j = h - 1; j >= 0; j--) eval(i >> j); } // call after touch seg[i] = data[i + n] void propUp(size_t i) { i += n; while(i >>= 1) eval(i * 2), eval(i * 2 + 1), data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]); } public: LazySegmentTree() : n(0) {} LazySegmentTree(size_t n, X initial = Monoid::identity()) : n(n) { if(n > 0) { h = 1; while(1u << h < n) h++; data.resize(2 * n, initial); lazy.resize(2 * n, M_act::identity()); nodeLength.resize(2 * n, 1); for(size_t i = n - 1; i > 0; i--) // fill from deep data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]), nodeLength[i] = nodeLength[i * 2] + nodeLength[i * 2 + 1]; } } template < class InputIter, class = typename iterator_traits< InputIter >::value_type > LazySegmentTree(InputIter first, InputIter last) : LazySegmentTree(distance(first, last)) { if(n > 0) { copy(first, last, begin(data) + n); for(size_t i = n - 1; i > 0; i--) // fill from deep data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]); } } LazySegmentTree(vector< X > v) : LazySegmentTree(v.begin(), v.end()) {} LazySegmentTree(initializer_list< X > v) : LazySegmentTree(v.begin(), v.end()) {} void act(int l, int r, const M &m) { if(l < 0) l = 0; if(l >= r) return; if(r > (int) n) r = n; evalDown(l); evalDown(r - 1); int tl = l, tr = r; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) eval(l), lazy[l] = m, eval(l), l++; if(r & 1) --r, eval(r), lazy[r] = m, eval(r); } propUp(tl); propUp(tr - 1); } void set(size_t i, const X &x) { assert(i < n); evalDown(i); data[i + n] = x; propUp(i); } X get(size_t i) { assert(i < n); evalDown(i); return data[i + n]; } X fold(int l, int r) { if(l < 0) l = 0; if(l >= r) return Monoid::identity(); if(r > (int) n) r = n; evalDown(l); evalDown(r - 1); X tmpL = Monoid::identity(), tmpR = Monoid::identity(); for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) eval(l), tmpL = Monoid::op(tmpL, data[l]), l++; if(r & 1) --r, eval(r), tmpR = Monoid::op(data[r], tmpR); } return Monoid::op(tmpL, tmpR); } int size() { return n; } inline void dum(int r = -1) { #ifdef DEBUG if(r < 0) r = n; DEBUG_OUT << "{"; for(int i = 0; i < min(r, (int) n); i++) DEBUG_OUT << (i ? ", " : "") << get(i); DEBUG_OUT << "}" << endl; #endif } }; /// }}}--- /// /// --- Monoid examples {{{ /// constexpr long long inf_monoid = 1e18 + 100; #include struct Nothing { using T = char; using Monoid = Nothing; using M = T; static constexpr T op(const T &, const T &) { return T(); } static constexpr T identity() { return T(); } template < class X > static constexpr X actInto(const M &, long long, const X &x) { return x; } }; template < class U = long long > struct RangeMin { using T = U; static T op(const T &a, const T &b) { return std::min< T >(a, b); } static constexpr T identity() { return T(inf_monoid); } }; template < class U = long long > struct RangeMax { using T = U; static T op(const T &a, const T &b) { return std::max< T >(a, b); } static constexpr T identity() { return T(-inf_monoid); } }; template < class U = long long > struct RangeSum { using T = U; static T op(const T &a, const T &b) { return a + b; } static constexpr T identity() { return T(0); } }; template < class U > struct RangeProd { using T = U; static T op(const T &a, const T &b) { return a * b; } static constexpr T identity() { return T(1); } }; template < class U = long long > struct RangeOr { using T = U; static T op(const T &a, const T &b) { return a | b; } static constexpr T identity() { return T(0); } }; #include template < class U = long long > struct RangeAnd { using T = U; static T op(const T &a, const T &b) { return a & b; } static constexpr T identity() { return T(-1); } }; template < size_t N > struct RangeAnd< std::bitset< N > > { using T = std::bitset< N >; static T op(const T &a, const T &b) { return a & b; } static constexpr T identity() { return std::bitset< N >().set(); } }; /// }}}--- /// /// --- M_act examples {{{ /// template < class U = long long, class V = U > struct RangeMinAdd { using X = U; using M = V; using Monoid = RangeMin< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long, const X &x) { return m + x; } }; template < class U = long long, class V = U > struct RangeMaxAdd { using X = U; using M = V; using Monoid = RangeMax< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long, const X &x) { return m + x; } }; template < class U = long long, class V = U > struct RangeMinSet { using M = U; using Monoid = RangeMin< U >; using X = typename Monoid::T; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeMaxSet { using M = U; using Monoid = RangeMax< U >; using X = typename Monoid::T; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeSumAdd { using X = U; using M = V; using Monoid = RangeSum< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long n, const X &x) { return m * n + x; } }; template < class U = long long, class V = U > struct RangeSumSet { using X = U; using M = V; using Monoid = RangeSum< U >; static M op(const M &a, const M &b) { return a == identity() ? a : b; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long n, const X &x) { return m == identity() ? x : m * n; } }; template < class U, class V = U > struct RangeProdMul { using X = U; using M = V; using Monoid = RangeProd< U >; static M mpow(M a, long long b) { X r(1); while(b) { if(b & 1) r = r * a; a = a * a; b >>= 1; } return r; } static M op(const M &a, const M &b) { return a * b; } static constexpr M identity() { return M(1); } static X actInto(const M &m, long long n, const X &x) { return x * mpow(m, n); } }; template < class U, class V = U > struct RangeProdSet { using X = U; using M = V; using Monoid = RangeProd< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return V::unused; } static X actInto(const M &m, long long n, const X &) { if(m == identity()) return; return RangeProdMul< U, V >::mpow(m, n); } }; template < class U = long long, class V = U > struct RangeOrSet { using X = U; using M = V; using Monoid = RangeOr< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeAndSet { using X = U; using M = V; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeOr2 { using X = U; using M = V; using Monoid = RangeOr< U >; static M op(const M &a, const M &b) { return a | b; } static constexpr M identity() { return M(0); } static X actInto(const M &m, long long, const X &x) { return m | x; } }; template < class U = long long, class V = U > struct RangeAnd2 { using X = U; using M = V; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a & b; } static constexpr M identity() { return M(-1); } static X actInto(const M &m, long long, const X &x) { return m & x; } }; template < class U, size_t N > struct RangeAnd2< U, std::bitset< N > > { using X = U; using M = std::bitset< N >; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a & b; } static constexpr M identity() { return std::bitset< N >().set(); } static X actInto(const M &m, long long, const X &x) { return m & x; } }; /// }}}--- /// using Seg = LazySegmentTree< RangeSumAdd<> >; int val[N]; void dfs(int i, int p = -1) { for(auto to : g[i]) if(to.first != p) { int j, w; tie(j, w) = to; dfs(j, i); val[j] = w; } } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n; g.resize(n); HLD hld(n); for(int i = 0; i < n - 1; i++) { int a, b, w; std::cin >> a >> b >> w; g[a].emplace_back(b, w); g[b].emplace_back(a, w); hld.add_edge(a, b); } dfs(0); hld.build(); Seg seg(n); for(int i = 0; i < n; i++) seg.set(hld[i], val[i]); int q; cin >> q; for(int i = 0; i < q; i++) { int t; cin >> t; if(t == 1) { int a, x; cin >> a >> x; seg.act(hld.in_exclusive(a), hld.out(a), x); } else { int b; cin >> b; ll ans = 0; hld.fold(0, b, [&ans, &seg](int l, int r){ ans += seg.fold(l, r); }, 0); cout << ans << "\n"; } } return 0; }