class LCA: def __init__(self, G, root=0): self.G = G self.root = root self.n = len(G) self.logn = (self.n - 1).bit_length() self.depth = [-1 if i != root else 0 for i in range(self.n)] self.parent = [[-1] * self.n for _ in range(self.logn)] self.dfs() self.doubling() def dfs(self): que = [self.root] while que: u = que.pop() for v in self.G[u]: if self.depth[v] == -1: self.depth[v] = self.depth[u] + 1 self.parent[0][v] = u que += [v] def doubling(self): for i in range(1, self.logn): for v in range(self.n): if self.parent[i - 1][v] != -1: self.parent[i][v] = self.parent[i - 1][self.parent[i - 1][v]] def get(self, u, v): if self.depth[v] < self.depth[u]: u, v = v, u du = self.depth[u] dv = self.depth[v] for i in range(self.logn): if (dv - du) >> i & 1: v = self.parent[i][v] if u == v: return u for i in range(self.logn - 1, -1, -1): pu, pv = self.parent[i][u], self.parent[i][v] if pu != pv: u, v = pu, pv return self.parent[0][u] def dist(self, u, v): return self.depth[u] + self.depth[v] - 2 * self.depth[self.get(u, v)] n = int(input()) edges = [[] for _ in range(n + 1)] for _ in range(n - 1): u, v = map(int, input().split()) edges[u].append(v) edges[v].append(u) edges[0].append(1) edges[1].append(0) lca = LCA(edges) imos = [0] * (n + 1) Q = int(input()) for _ in range(Q): a, b = map(int, input().split()) p = lca.get(a, b) imos[b] += 1 imos[a] += 1 imos[p] -= 1 imos[lca.parent[0][p]] -= 1 route = [0] stack = [0] used = [False] * (n + 1) used[0] = True while stack: pos = stack.pop() for npos in edges[pos]: if used[npos]: continue used[npos] = True stack.append(npos) route.append(npos) used = [False] * (n + 1) for pos in route[::-1]: used[pos] = True for npos in edges[pos]: if not used[npos]: continue imos[pos] += imos[npos] ans = 0 for i in imos: ans += i * (i + 1) // 2 print(ans)