#頂点は1-index,下段は0-index class LazySegTree: #単位元と結合と作用をここで定義 Xunit = (0,0) Aunit = 0 def Xf(self,x,y): return (x[0]+y[0],x[1]+y[1]) #Xf = max def Af(self,a,b): return a + b #AのXへの作用 def operate(self,x,a): return (x[0] + x[1] * a,x[1]) def __init__(self,N): self.N = N self.X = [self.Xunit] * (N + N) self.A = [self.Aunit] * (N + N) def build(self,seq): for i,x in enumerate(seq,self.N): self.X[i] = x for i in range(self.N-1,0,-1): self.X[i] = self.Xf(self.X[i<<1],self.X[i<<1 | 1]) def eval_at(self,i): return self.operate(self.X[i],self.A[i]) def propagate_at(self,i): self.X[i] = self.eval_at(i) self.A[i<<1] = self.Af(self.A[i<<1],self.A[i]) self.A[i<<1 | 1] = self.Af(self.A[i<<1 | 1],self.A[i]) self.A[i] = self.Aunit def propagate_above(self,i): H = i.bit_length() - 1 for h in range(H,0,-1): self.propagate_at(i >> h) def recalc_above(self,i): while i > 1: i >>= 1 self.X[i] = self.Xf(self.eval_at(i << 1),self.eval_at(i << 1 | 1)) def update(self,i,x): i += self.N self.propagate_above(i) self.X[i] = x self.A[i] = self.Aunit self.recalc_above(i) def fold(self,L = 0,R = -1): if R == -1:R = self.N L += self.N R += self.N self.propagate_above(L // (L & -L)) self.propagate_above(R // (R & -R) -1) vL = self.Xunit vR = self.Xunit while L < R: if L & 1: vL = self.Xf(vL,self.eval_at(L)) L += 1 if R & 1: R -= 1 vR = self.Xf(self.eval_at(R),vR) L >>= 1 R >>= 1 return self.Xf(vL,vR) def operate_range(self,L,R,x): #区間全体に作用させる L += self.N R += self.N L0 = L // (L & -L) R0 = R // (R & -R) - 1 self.propagate_above(L0) self.propagate_above(R0) while L < R: if L & 1: self.A[L] = self.Af(self.A[L],x) L += 1 if R & 1: R -= 1 self.A[R] = self.Af(self.A[R],x) L >>= 1 R >>= 1 self.recalc_above(L0) self.recalc_above(R0) def write(self): print(self.X) def change(self,Xf,Xunit,Af,Aunit,operate): self.Xf = Xf self.Xunit = Xunit self.Af = Af self.Aunit = Aunit self.operate = operate #HL分解 class HL: #u,vを結ぶpathへのクエリはここにでも # f は区間 [l,r)に対するクエリ def f(self,l,r): pass def merge(self,x,y): return x + y def __init__(self,G,root): self.G = G self.root = root self.N = len(G) self.size = [1] * self.N #部分木のサイズ self.p = [0] * self.N #親頂点 self.H = [None] * self.N #Heavy_edgeでつながる子頂点。葉ではNoneが入ってる self._in = [-1] * self.N #最初に探索したときの位置 self.out = [-1] * self.N #部分木をでるタイミング。オイラーとはちょっと違う。 #開区間 [_in[i],out[i]) がiの部分木に対応 self.pathtop = [0] * self.N #iの属するpathの中で最も根に近い頂点。代表にする self.build() self.build_path() def build(self): stack = [(~self.root,-1),(self.root,-1)] G = self.G size = self.size H = self.H while stack: now,parent = stack.pop() if now < 0: now = ~now _max = 0 for v in G[now]: if v == parent:continue size[now] += size[v] if size[v] > _max: _max = size[v] H[now] = v else: for v in G[now]: if v == parent:continue self.p[v] = now stack.append((~v,now)) stack.append((v,now)) def build_path(self): stack = [(~self.root,-1,self.root),(self.root,-1,self.root)] count = 0 G = self.G H = self.H while stack: now,parent,top = stack.pop() if now >= 0: self._in[now] = count count += 1 self.pathtop[now] = top h = H[now] if h is None:continue for v in G[now]: if v == parent or v == h:continue stack.append((~v,now,v)) stack.append((v,now,v)) stack.append((~h,now,top)) stack.append((h,now,top)) else: now = ~now self.out[now] = count #最近共通先祖 def lca(self,a,b): pathtop = self.pathtop _in = self._in pa = pathtop[a] pb = pathtop[b] while pa != pb: if _in[pa] > _in[pb]: a = self.p[pa] pa = pathtop[a] else: b = self.p[pb] pb = pathtop[b] return a if _in[a] < _in[b] else b def subtree_query(self,a,f = None): #if f is None:f = self.f return f(self._in[a],self.out[a]) def subtree_array(self,a): return (self._in[a],self.out[a]) #下のpath_arrayとほぼ同じ。タプルを一つだけ返す #f = lambda l,r:seg.fold(l,r) とか #f = lambda l,r:seg.oparete_range(l,r,x) とか #代入して使う def path_query(self,a,b,f = None,merge = None): #if f is None:f = self.f #if merge is None:merge = self.merge pathtop = self.pathtop p = self.p _in = self._in pa = pathtop[a] pb = pathtop[b] ans = 0 while pa != pb: if _in[pa] > _in[pb]: ans = merge(ans,f(_in[pa],_in[a]+1)) a = p[pa] pa = pathtop[a] else: ans = merge(ans,f(_in[pb],_in[b]+1)) b = p[pb] pb = pathtop[b] if _in[a] > _in[b]: a,b = b,a ans = merge(ans,f(_in[a],_in[b]+1)) return ans # a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも #半開区間 [l,r) の集まりを返す #現状順番は適当 #こっちのほうが早かった def path_array(self,a,b): pathtop = self.pathtop p = self.p _in = self._in ans = [] pa = pathtop[a] pb = pathtop[b] while pa != pb: if _in[pa] > _in[pb]: ans.append((_in[pa],_in[a]+1)) a = p[pa] pa = pathtop[a] else: ans.append((_in[pb],_in[b]+1)) b = p[pb] pb = pathtop[b] if _in[a] > _in[b]: a,b = b,a ans.append((_in[a],_in[b]+1)) return ans import sys rr = sys.stdin N = int(rr.readline()) G = [[] for _ in range(N)] edge = [] for _ in range(N-1): u,v,w = map(int,rr.readline().split()) G[u].append(v) G[v].append(u) edge.append((u,v,w)) hl = HL(G,0) seg = LazySegTree(N) seq = [(0,0)] * N for u,v,w in edge: if hl.p[u] == v: seq[hl._in[u]] = (w,1) else: seq[hl._in[v]] = (w,1) seg.build(seq) Q = int(rr.readline()) for _ in range(Q): t,*ll = map(int,rr.readline().split()) if t == 1: l,r = hl.subtree_array(ll[0]) seg.operate_range(l+1,r,ll[1]) else: ans = 0 L = hl.path_array(0,ll[0]) for l,r in L: ans += seg.fold(l,r)[0] print(ans)