class Tree(): def __init__(self, n, edge): self.n = n self.tree = [[] for _ in range(n)] for e in edge: self.tree[e[0] - 1].append(e[1] - 1) self.tree[e[1] - 1].append(e[0] - 1) def setroot(self, root): self.root = root self.parent = [None for _ in range(self.n)] self.parent[root] = -1 self.depth = [None for _ in range(self.n)] self.depth[root] = 0 self.order = [] self.order.append(root) self.size = [1 for _ in range(self.n)] stack = [root] while stack: node = stack.pop() for adj in self.tree[node]: if self.parent[adj] is None: self.parent[adj] = node self.depth[adj] = self.depth[node] + 1 self.order.append(adj) stack.append(adj) for node in self.order[::-1]: for adj in self.tree[node]: if self.parent[node] == adj: continue self.size[node] += self.size[adj] def heavylight_decomposition(self): self.order = [None for _ in range(self.n)] self.head = [None for _ in range(self.n)] self.head[self.root] = self.root self.next = [None for _ in range(self.n)] stack = [self.root] order = 0 while stack: node = stack.pop() self.order[node] = order order += 1 maxsize = 0 for adj in self.tree[node]: if self.parent[node] == adj: continue if maxsize < self.size[adj]: maxsize = self.size[adj] self.next[node] = adj for adj in self.tree[node]: if self.parent[node] == adj or self.next[node] == adj: continue self.head[adj] = adj stack.append(adj) if self.next[node] is not None: self.head[self.next[node]] = self.head[node] stack.append(self.next[node]) def range_hld(self, u, v, edge=False): res = [] while True: if self.order[u] > self.order[v]: u, v = v, u if self.head[u] != self.head[v]: res.append((self.order[self.head[v]], self.order[v] + 1)) v = self.parent[self.head[v]] else: res.append((self.order[u] + edge, self.order[v] + 1)) return res def lca_hld(self, u, v): while True: if self.order[u] > self.order[v]: u, v = v, u v = self.parent[self.head[v]] return u class SegmentTreeLazy(): def __init__(self, arr, ti, ei, func, op, merge): self.h = (len(arr) - 1).bit_length() self.n = 2**self.h self.func = func self.op = op self.merge = merge self.ti = ti self.ei = ei self.val = [ti for _ in range(2 * self.n)] for i in range(len(arr)): self.val[self.n + i] = arr[i] for i in range(1, self.n)[::-1]: self.val[i] = self.func(self.val[2 * i], self.val[2 * i + 1]) self.laz = [ei for _ in range(2 * self.n)] def reflect(self, k): if self.laz[k] == self.ei: return self.val[k] return self.op(self.val[k], self.laz[k]) def propagate(self, k): if self.laz[k] == self.ei: return self.laz[2 * k] = self.merge(self.laz[2 * k], self.laz[k]) self.laz[2 * k + 1] = self.merge(self.laz[2 * k + 1], self.laz[k]) self.val[k] = self.reflect(k) self.laz[k] = self.ei def thrust(self, k): for i in range(1, self.h + 1)[::-1]: self.propagate(k >> i) def recalc(self, k): while k: k >>= 1 self.val[k] = self.func(self.reflect(2 * k), self.reflect(2 * k + 1)) def update(self, lt, rt, x): lt += self.n rt += self.n vl = lt vr = rt self.thrust(lt) self.thrust(rt - 1) while rt - lt > 0: if lt & 1: self.laz[lt] = self.merge(self.laz[lt], x) lt += 1 if rt & 1: rt -= 1 self.laz[rt] = self.merge(self.laz[rt], x) lt >>= 1 rt >>= 1 self.recalc(vl) self.recalc(vr - 1) def query(self, lt, rt): lt += self.n rt += self.n self.thrust(lt) self.thrust(rt - 1) vl = vr = self.ti while rt - lt > 0: if lt & 1: vl = self.func(vl, self.reflect(lt)) lt += 1 if rt & 1: rt -= 1 vr = self.func(self.reflect(rt), vr) lt >>= 1 rt >>= 1 return self.func(vl, vr) import sys input = sys.stdin.readline N = int(input()) E = [tuple(map(int, input().split())) for _ in range(N - 1)] T = Tree(N, E) T.setroot(0) T.heavylight_decomposition() st = SegmentTreeLazy( arr = [(0, 1) for _ in range(N)], ti = (0, 1), ei = 0, func = lambda a, b: (a[0] + b[0], a[1] + b[1]), op = lambda a, x: (a[0] + a[1] * x, a[1]), merge = lambda x, y : x + y ) Q = int(input()) res = 0 for _ in range(Q): a, b = map(int, input().split()) for lt, rt in T.range_hld(a - 1, b - 1): st.update(lt, rt, 1) res += st.query(lt, rt)[0] print(res)