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 = [-1] * 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.flod(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 def path_array(self,a,b): # a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも #半開区間 [l,r) の集まりを返す #現状順番は適当 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 class LazyPropSegmentTree: def __init__(self, lst, op, apply, comp, e, identity): self.n = len(lst) self.depth = (self.n - 1).bit_length() self.N = 1 << self.depth self.op = op # binary operation of elements self.apply = apply # function to apply to an element self.comp = comp # composition of functions self.e = e # identity element w.r.t. op self.identity = identity # identity element w.r.t. comp self.v, self.length = self._build(lst) # self.v is set to be 1-indexed for simplicity self.lazy = [self.identity] * (2 * self.N) def __getitem__(self, i): return self.fold(i, i+1) def _build(self, lst): # construction of a tree # total 2 * self.N elements (tree[0] is not used) e, N, op = self.e, self.N, self.op tree = [e] * N + lst + [e] * (N - self.n) length = [1] * (2 * N) for i in range(N - 1, 0, -1): lc, rc = i << 1, (i << 1)|1 tree[i] = op(tree[lc], tree[rc]) length[i] = length[lc] + length[rc] return tree, length def _indices(self, l, r): left = l + self.N; right = r + self.N left //= (left & (-left)); right //= (right & (-right)) left >>= 1; right >>= 1 while left != right: if left > right: yield left; left >>= 1 else: yield right; right >>= 1 while left > 0: yield left; left >>= 1 # propagate self.lazy and self.v in a top-down manner def _propagate_topdown(self, *indices): identity, v, lazy, length, apply, comp = self.identity, self.v, self.lazy, self.length, self.apply, self.comp for k in reversed(indices): x = lazy[k] if x == identity: continue lc, rc = k << 1, (k << 1) | 1 lazy[lc] = comp(lazy[lc], x) lazy[rc] = comp(lazy[rc], x) v[lc] = apply(v[lc], x, length[lc]) v[rc] = apply(v[rc], x, length[rc]) lazy[k] = identity # propagated # propagate self.v in a bottom-up manner def _propagate_bottomup(self, indices): v, op = self.v, self.op for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1]) # update for the query interval [l, r) with function x def update(self, l, r, x): *indices, = self._indices(l, r) self._propagate_topdown(*indices) N, v, lazy, length, apply, comp = self.N, self.v, self.lazy, self.length, self.apply, self.comp # update self.v and self.lazy for the query interval [l, r) left = l + N; right = r + N if left & 1: v[left] = apply(v[left], x, length[left]); left += 1 if right & 1: right -= 1; v[right] = apply(v[right], x, length[right]) left >>= 1; right >>= 1 while left < right: if left & 1: lazy[left] = comp(lazy[left], x) v[left] = apply(v[left], x, length[left]) left += 1 if right & 1: right -= 1 lazy[right] = comp(lazy[right], x) v[right] = apply(v[right], x, length[right]) left >>= 1; right >>= 1 self._propagate_bottomup(indices) # returns answer for the query interval [l, r) def fold(self, l, r): self._propagate_topdown(*self._indices(l, r)) e, N, v, op = self.e, self.N, self.v, self.op # calculate the answer for the query interval [l, r) left = l + N; right = r + N L = R = e while left < right: if left & 1: # self.v[left] is the right child L = op(L, v[left]) left += 1 if right & 1: # self.v[right-1] is the left child right -= 1 R = op(v[right], R) left >>= 1; right >>= 1 return op(L, R) N = int(input()) G = [[] for _ in range(N+1)] for _ in range(N-1): a,b = map(int,input().split()) G[a-1].append(b-1) G[b-1].append(a-1) hl = HL(G,1) """ print(hl._in) print(hl.p) print(hl.pathtop) """ Q = int(input()) seq = [1] * N op = lambda x, y: x+y apply = lambda x, f, l: x + f*l comp = lambda f, g: f + g e = 0 identity = 0 A = seq lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity) ans = [] for _ in range(Q): *arg, = map(int, input().split()) s, t= arg lpsg.update(s-1, t, 1) ans.append(lpsg.fold(s-1, t)) print(sum(ans))