class LazySegTree: def __init__(self, N): self.N = N self._N = 1 << ((N - 1).bit_length()) self.Vele = 0 self.Eele = 0 self.node = [0] * 2 * self._N self.lazy = [0] * 2 * self._N self.F = lambda x, y: x + y self.G = lambda v, E, idx: v + E * (self._N >> (idx+1).bit_length() - 1) self.H = lambda p, q: p + q def build(self, lis): for i in range(self.N): self.node[i + self._N - 1] = lis[i] for i in range(self._N - 2, -1, -1): self.node[i] = self.F(self.node[i * 2 + 1], self.node[i * 2 + 2]) def _gindex(self, l, r): left = l + self._N right = r + self._N lm = (left // (left & -left)) >> 1 rm = (right // (right & -right)) >> 1 while left < right: if right <= rm: yield right if left <= lm: yield left left >>= 1 right >>= 1 while left: yield left left >>= 1 def propagates(self, *ids): # ids: 1-indexded for i in reversed(ids): E = self.lazy[i - 1] if E is self.Eele: continue self.lazy[2 * i - 1] = self.H(self.lazy[2 * i - 1], E) self.node[2 * i - 1] = self.G(self.node[2 * i - 1], E, 2 * i - 1) self.lazy[2 * i] = self.H(self.lazy[2 * i], E) self.node[2 * i] = self.G(self.node[2 * i], E, 2 * i + 1) self.lazy[i - 1] = self.Eele return def update(self, l, r, E): *ids, = self._gindex(l, r) self.propagates(*ids) left = l + self._N right = r + self._N while left < right: if left & 1: self.lazy[left - 1] = self.H(self.lazy[left - 1], E) self.node[left - 1] = self.G(self.node[left - 1], E, left - 1) left += 1 if right & 1: right -= 1 self.lazy[right - 1] = self.H(self.lazy[right - 1], E) self.node[right - 1] = self.G(self.node[right - 1], E, right - 1) left >>= 1 right >>= 1 for i in ids: self.node[i - 1] = self.F(self.node[2 * i - 1], self.node[2 * i]) def query(self, l, r): self.propagates(*self._gindex(l, r)) left = l + self._N right = r + self._N retl = self.Vele retr = self.Vele while left < right: if right & 1: right -= 1 retr = self.F(self.node[right - 1], retr) if left & 1: retl = self.F(retl, self.node[left - 1]) left += 1 left >>= 1 right >>= 1 return self.F(retl, retr) class HLDecomposition: def __init__(self, N): self.N = N self.pos = 0 self.G = [list() for _ in range(N)] self.vid = [-1] * N self.head = [0] * N self.sub = [1] * N self.hvy = [-1] * N self.par = [-1] * N self.dep = [0] * N self.inv = [0] * N self.rng = [0] * N # subtree of v -> [vid[v], rng[v]) def add_edge(self, u, v): self.G[u].append(v) self.G[v].append(u) return def build(self, rs = (0, )): for r in rs: self._dfs(r) self._dfs_hld(r) return def _dfs(self, rt): self.par[rt] = -1 self.dep[rt] = 0 st = list(); st.append([rt, 0]) while st: v, i = st[-1] if i < len(self.G[v]): u = self.G[v][i] st[-1][1] += 1 if u == self.par[v]: continue self.par[u] = v self.dep[u] = self.dep[v] + 1 st.append([u, 0]) else: st.pop() res = 0 for u in self.G[v]: if u == self.par[v]: continue self.sub[v] += self.sub[u] if res < self.sub[u]: res = self.sub[u] self.hvy[v] = u return def _dfs_hld(self, r): q = [r] while q: v = q[-1] if self.vid[v] < 0: self.vid[v] = self.pos self.pos += 1 self.inv[self.vid[v]] = v self.head[v] = v if self.hvy[self.par[v]] == v: self.head[v] = self.head[self.par[v]] for u in self.G[v]: if u != self.par[v] and u != self.hvy[v]: q.append(u) if self.hvy[v] >= 0: q.append(self.hvy[v]) else: q.pop() self.rng[v] = self.pos return def for_each_vertex(self, u, v): while True: if self.vid[u] > self.vid[v]: u, v = v, u yield (max(self.vid[self.head[v]], self.vid[u]), self.vid[v]) if self.head[u] != self.head[v]: v = self.par[self.head[v]] else: break return # [u, v] def for_each_edge(self, u, v, func): while True: if self.vid[u] > self.vid[v]: u, v = v, u if self.head[u] != self.head[v]: func(self.vid[self.head[v]], self.vid[v]) v = self.par[self.head[v]] elif u != v: func(self.vid[u] + 1, self.vid[v]) break return def subtree_range(self, v): # Need Repair return (self.vid[v], self.rng[v]) n = int(input()) hld = HLDecomposition(n) for _ in range(n-1): u, v = map(int, input().split()) hld.add_edge(u-1, v-1) hld.build() q = int(input()) seg = LazySegTree(n) res = 0 for _ in range(q): a, b = map(int, input().split()) for u, v in hld.for_each_vertex(a-1, b-1): seg.update(u, v+1, 1) res += seg.query(u, v+1) print(res)