import sys import math sys.setrecursionlimit(10**6) input = raw_input range = xrange def read_data(): N = int(input()) Es = [[] for i in range(N)] for i in range(N - 1): u, v = map(int, input().split()) u -= 1 v -= 1 Es[u].append(v) Es[v].append(u) Q = int(input()) moves = [] for i in range(Q): a, b = map(int, input().split()) moves.append((a - 1, b - 1)) return N, Es, Q, moves class Tree(): def __init__(self, N, Es, root): self.n = N self.root = root self.child = [[] for i in range(N)] self._set_child(Es) def _set_child(self, Es): que = [self.root] visited = [False] * self.n while que: v = que.pop() for u in Es[v]: if visited[u]: continue self.child[v].append(u) que.append(u) visited[v] = True class LCArmq(): def __init__(self, tree): D, E, R = self._convert_to_RMQ(tree.child, tree.root, tree.n) self._euler = E self._reverse = R self._RMQ = RMQ(D) def _convert_to_RMQ(self, child, root, n): ''' LCA の前処理。 RMQ に置き換えるため、Euler tour で巡回して深さのリストをつくる。 ''' depth = [] euler = [] reverse = [0] * n def euler_tour(node, d, depth, euler): for v in child[node]: euler.append(node) depth.append(d) euler_tour(v, d + 1, depth, euler) euler.append(node) depth.append(d) euler_tour(root, 0, depth, euler) for i, node in enumerate(euler): reverse[node] = i return depth, euler, reverse def query(self, v, w): i, j = self._reverse[v], self._reverse[w] rmq = self._RMQ.query(i, j) lca = self._euler[rmq] return lca class RMQ(): def __init__(self, A): self._A = A self._preprocess() def _preprocess(self): ''' RMQ の前処理。 ''' n = len(self._A) max_j = int(math.log(n, 2)) self._M = [list(range(n))] for j in range(0, max_j): shift = 1 << j Mj = self._M[j] Mjnext = [] for k1, k2 in zip(Mj, Mj[shift:]): k = k1 if self._A[k1] < self._A[k2] else k2 Mjnext.append(k) self._M.append(Mjnext) def query(self, i, j): if i == j: return i if i > j: i, j = j, i el = int(math.log(j - i, 2)) k1 = self._M[el][i] k2 = self._M[el][j - (1 << el) + 1] rmq = k1 if self._A[k1] < self._A[k2] else k2 return rmq def solve(N, Es, Q, moves): global imos1, imos2, imos3 tree = Tree(N, Es, 0) lca_rmq = LCArmq(tree) imos1 = [0] * N imos2 = [0] * N for a, b in moves: v = lca_rmq.query(a, b) imos1[a] += 1 imos1[b] += 1 imos1[v] -= 2 imos2[v] += 1 imos3 = [0] * N dfs(0, tree.child) return count_tax(imos3, imos2, N) def dfs(u, child): global imos3 ret = imos1[u] for v in child[u]: ret += dfs(v, child) imos3[u] = ret return ret def count_tax(imos3, imos2, N): tax = 0 for i in range(N): t = imos3[i] + imos2[i] tax += t * (t + 1) return tax // 2 N, Es, Q, moves = read_data() print(solve(N, Es, Q, moves))