#include using namespace std; //SegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), h は作用素同士をマージする二項演算, M1 はモノイドの単位元, OM0は 作用素の単位元である。 //update(a, b, x) := 区間 [a,b) に作用素 xを適用する。 template< typename Monoid, typename OperatorMonoid = Monoid > struct LazySegmentTree { using F = function< Monoid(Monoid, Monoid) >; using G = function< Monoid(Monoid, OperatorMonoid, int) >; using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >; int sz; vector< Monoid > data; vector< OperatorMonoid > lazy; const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; while(sz < n) sz <<= 1; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void set(int k, const Monoid &x) { data[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { data[k] = f(data[2 * k + 0], data[2 * k + 1]); } } void propagate(int k, int len) { if(lazy[k] != OM0) { if(k < sz) { lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); } data[k] = g(data[k], lazy[k], len); lazy[k] = OM0; } } Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) { propagate(k, r - l); if(r <= a || b <= l) { return data[k]; } else if(a <= l && r <= b) { lazy[k] = h(lazy[k], x); propagate(k, r - l); return data[k]; } else { return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1), update(a, b, x, 2 * k + 1, (l + r) >> 1, r)); } } Monoid update(int a, int b, const OperatorMonoid &x) { return update(a, b, x, 1, 0, sz); } Monoid query(int a, int b, int k, int l, int r) { propagate(k, r - l); if(r <= a || b <= l) { return M1; } else if(a <= l && r <= b) { return data[k]; } else { return f(query(a, b, 2 * k + 0, l, (l + r) >> 1), query(a, b, 2 * k + 1, (l + r) >> 1, r)); } } Monoid query(int a, int b) { return query(a, b, 1, 0, sz); } Monoid operator[](const int &k) { return query(k, k + 1); } }; //SegmentTree(n, f, g, h, M1, OM0):= サイズ n の初期化。ここで f は2つの区間の要素をマージする二項演算, g は要素と作用素をマージする二項演算(第三引数は対応する区間の長さ), h は作用素同士をマージする二項演算, M1 はモノイドの単位元, OM0は 作用素の単位元である。 #define N 200010 #define int long long struct LazySegmentTree, int> segtree(N, [](pair a, pair b){ return make_pair(a.first + b.first, a.second + b.second);}, [](pair a, int b, int z){ return make_pair(a.first + a.second * b, a.second);}, [](int a, int b){ return a + b; }, make_pair(0, 0), 0); int ds[N]; int us[N]; vector> graph[100010]; void dfs(int v, int p, int &k){ for(auto u : graph[v]){ if(u.first == p) continue; ds[u.first] = k++; segtree.set(ds[u.first], {u.second, 1}); dfs(u.first, v, k); us[u.first] = k++; segtree.set(us[u.first], {-u.second, -1}); } } signed main(){ int n; cin >> n; for(int i = 0;i < n-1;i++){ int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); } int num = 1; ds[0] = -1; dfs(0, -1, num); us[0] = num; segtree.build(); int q; cin >> q; while(q--){ int query, a, x; cin >> query; if(query == 1){ cin >> a >> x; segtree.update(ds[a]+1, us[a]+1, x); }else{ cin >> a; cout << segtree.query(0, ds[a]+1).first << endl; } } return 0; };