package main import ( "bufio" "fmt" "os" "reflect" "strconv" ) var wg = bufio.NewScanner(os.Stdin) const ( inf = int(1e18) initialBufSize = int(1e6) maxBufSize = int(1e6) ) var buf []byte = make([]byte, initialBufSize) type edge struct { u, v, w int } type Graph struct { n int edges [][]edge } func NewGraph(n int) *Graph { g := &Graph{ n: n, edges: make([][]edge, n), } for i := 0; i < n; i++ { g.edges[i] = make([]edge, 0) } return g } func euler_tour(g *Graph, S int) ([]int, []int, []int, []int, []int) { DIST, par := make([]int, g.n), make([]int, g.n) path := make([]int, 0) for i := 0; i < g.n; i++ { DIST[i] = inf par[i] = -1 } DIST[S] = 0 //再帰関数 var dfs func(s int) IN, OUT := make([]int, g.n), make([]int, g.n) inc := 0 dfs = func(s int) { path = append(path, s) IN[s] = inc for _, e := range g.edges[s] { if DIST[e.v] == inf { DIST[e.v] = DIST[s] + e.w par[e.v] = s inc++ dfs(e.v) } } inc++ p := par[s] if p != -1 { path = append(path, p) } OUT[s] = inc } dfs(0) return IN, OUT, DIST, path, par } func main() { n := nextInt() g := NewGraph(n) for i := 0; i < n-1; i++ { u, v, w := nextInt(), nextInt(), nextInt() g.edges[u] = append(g.edges[u], edge{u, v, w}) g.edges[v] = append(g.edges[v], edge{v, u, w}) } //euler_tour IN, OUT, DIST, Path, Par := euler_tour(g, 0) seg, _ := Gen(Monoid{}, op_Monoid(0), binary_op, S_Op, S_Ide, F_Op, F_Ide, 2*n-2) A := make([]Monoid, 2*n-2) for i := 0; i < 2*n-2; i++ { if Par[Path[i+1]] == Path[i] { A[i] = Monoid{cnt: 1, sum: 0} } else { A[i] = Monoid{cnt: -1, sum: 0} } } SliceGen(seg, A) q := nextInt() for i := 0; i < q; i++ { switch nextInt() { case 1: node, val := nextInt(), nextInt() seg.Apply(IN[node], OUT[node]-1, op_Monoid(val)) case 2: node := nextInt() ans := DIST[node] + seg.Prod(0, IN[node]).sum fmt.Printf("%d\n", ans) } } } type Monoid struct { cnt, sum int } func S_Op(x, y Monoid) Monoid { return Monoid{x.cnt + y.cnt, x.sum + y.sum} } func S_Ide() Monoid { return Monoid{0, 0} } //////////////////////////////////////////////////////// //Definition of Monoid F. type op_Monoid int func F_Op(x, y op_Monoid) op_Monoid { return op_Monoid(int(x) + int(y)) } func F_Ide() op_Monoid { return op_Monoid(0) } //////////////////////////////////////////////////////// //binary opearation S x F -> S func binary_op(x Monoid, f op_Monoid) Monoid { return Monoid{x.cnt, x.cnt*int(f) + x.sum} } type LazySegTree struct { monoid_type Monoid operator_monoid_type op_Monoid //要素の演算定義 op func(Monoid, Monoid) Monoid /* S x S-> S */ e func() Monoid /*identity op of S (value-monoid)*/ //作用素の演算定義 operator_op func(op_Monoid, op_Monoid) op_Monoid /*f x f -> f*/ operator_e func() op_Monoid /*identity op of F(opearator-monoid)*/ //作用素と要素の演算定義(右作用) binary_op func(Monoid, op_Monoid) Monoid /* S x F -> S */ d []Monoid _d []Monoid _lz []op_Monoid n int /* size*/ log int size int } func Gen(monoid Monoid, op_monoid op_Monoid, binary_op_monoid func(Monoid, op_Monoid) Monoid, S_op func(Monoid, Monoid) Monoid, S_e func() Monoid, F_op func(op_Monoid, op_Monoid) op_Monoid, F_e func() op_Monoid, n int) (LazySegTree, bool) { seg := LazySegTree{monoid_type: monoid, operator_monoid_type: op_monoid, op: S_op, e: S_e, operator_op: F_op, operator_e: F_e, binary_op: binary_op_monoid, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0} collect := true switch n > 0 { case true: seg.d = make([]Monoid, n) for i := range seg.d { seg.d[i] = seg.e() } default: collect = false return seg, collect } seg.n = len(seg.d) for ord := uint(0); (1 << ord) < seg.n; { ord++ seg.log = int(ord) } seg.size = 1 << uint(seg.log) seg._d = make([]Monoid, 2*seg.size) seg._lz = make([]op_Monoid, seg.size) for i := range seg._d { seg._d[i] = seg.e() } for i := range seg._lz { seg._lz[i] = seg.operator_e() } for i := 0; i < seg.n; i++ { seg._d[seg.size+i] = seg.d[i] } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return seg, collect } func SliceGen(seg LazySegTree, array []Monoid) bool { ok := true if len(array) != seg.n { ok = false return ok } for _, v := range array { if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) { ok = false return ok } } for i := 0; i < seg.n; i++ { seg._d[seg.size+i] = array[i] } for i := seg.size - 1; i > 0; i-- { seg._update(i) } return ok } func (seg LazySegTree) _update(k int) { seg._d[k] = seg.op(seg._d[2*k], seg._d[2*k+1]) } func (seg LazySegTree) _all_apply(k int, f op_Monoid) { seg._d[k] = seg.binary_op(seg._d[k], f) if k < seg.size { seg._lz[k] = seg.operator_op(seg._lz[k], f) } } func (seg LazySegTree) _push(k int) { seg._all_apply(k<<1, seg._lz[k]) seg._all_apply((k<<1)+1, seg._lz[k]) seg._lz[k] = seg.operator_e() } func (seg LazySegTree) Set(p int, x Monoid) { //a[p] -> x in O(logN). p += seg.size for i := uint(seg.log); i > 0; i-- { seg._push(p >> i) } seg._d[p] = x for i := uint(1); i <= uint(seg.log); i++ { seg._update(p >> i) } } func (seg LazySegTree) Get(p int) Monoid { // a[p] in O(logN). p += seg.size for i := uint(seg.log); i > 0; i-- { seg._push(p >> i) } return seg._d[p] } func (seg LazySegTree) GetThemAll() []Monoid { //get all element in O(N). for i := 0; i < seg.size; i++ { seg._push(i) } a := make([]Monoid, seg.n) for i := 0; i < seg.n; i++ { a[i] = seg._d[i+seg.size] } return a } func (seg LazySegTree) Prod(l, r int) Monoid { //a[l..r) in O(logN). sml := seg.e() smr := seg.e() l += seg.size r += seg.size for i := uint(seg.log); i > 0; i-- { if (l>>i)<> i) } if (r>>i)<> i) } } for l < r { if l&1 == 1 { sml = seg.op(sml, seg._d[l]) l++ } if r&1 == 1 { r-- smr = seg.op(seg._d[r], smr) } l >>= 1 r >>= 1 } return seg.op(sml, smr) } func (seg LazySegTree) AllProd() Monoid { return seg._d[1] } func (seg LazySegTree) Apply(l, r int, f op_Monoid) { // a[l..r) -> f(a[l..r)) in O(logN). l += seg.size r += seg.size for i := uint(seg.log); i > 0; i-- { if (l>>i)<> i) } if (r>>i)<> i) } } l2, r2 := l, r for l < r { if l&1 == 1 { seg._all_apply(l, f) l++ } if r&1 == 1 { r-- seg._all_apply(r, f) } l >>= 1 r >>= 1 } l, r = l2, r2 for i := uint(1); i <= uint(seg.log); i++ { if (l>>i)<> i) } if (r>>i)<> i) } } } func init() { wg.Split(bufio.ScanWords) wg.Buffer(buf, maxBufSize) } func nextInt() int { wg.Scan() i, e := strconv.Atoi(wg.Text()) if e != nil { panic(e) } return i }