#yukicoder 399 動的な領主 #online static LCA class Linear_LCA: def __init__(self, N, G, root = 0): self._N = N; self._G = G; self._root = root; self._index = index = [0] * 2 * N; self._visit = visit = [-1] * N; self._depth = depth = [0] * 2 * N; self._mask = (1<<30) - 1; stack = [(root, -1, 0)]; M, logM = 2 * N, (2 * N).bit_length(); self._size = size = logM // 2; m, logm = -(-M // size), ( -(M // size) ).bit_length(); self._T = T = [[9 * 10 ** 18] * logm for _ in range(m)]; self._B = B = [0] * m; self._D = D = [None] * (1 << size - 1); has_bit = lambda S,x: S >> x & 1 #ライブラリ改変 1/2: parentを配列定義 self.parent = [-1] * N for i in range(2 * N): #Euler Tour index[i]: (d << 30) + v now, back, d = stack.pop() if now >= 0: #ライブラリ改変 2/2: parentを記録 self.parent[now] = back stack.append((~now, back, d)); index[i], visit[now], depth[i] = (d << 30) + now, i, d for nxt in G[now]: if visit[nxt] == -1: stack.append((nxt, now, d + 1)) else: index[i], depth[i] = ((d-1) << 30) + back, d - 1 for S in range(1 << size - 1): #S: ibit目が1なら、depth[i] - 1 == depth[i+1] D[S] = dp = [[L] * size for L in range(size)] #dp[L][R]: 最小値を満たす添字 for Lt in range(size): x = y = 0 for Rt in range(Lt + 1, size): y = y - 1 if has_bit(S, Rt - 1) else y + 1; dp[Lt][Rt] = dp[Lt][Rt - 1]; x, dp[Lt][Rt] = (y, Rt) if x > y else (x, dp[Lt][Rt]) for b in range(m): Lt, Rt = size * b, min(size * (b + 1), M); T[b][0] = min(index[Lt:Rt]) for i in range(Rt - Lt - 1): B[b] += 1 << i if depth[Lt + i] - 1 == depth[Lt + i + 1] else 0 for j in range(logm - 1): mid = 1 << j for i in range(m): T[i][j+1] = min(T[i][j],T[i+mid][j]) if i+mid= Rt else min( self._T[Lt][d], self._T[Rt - (1 << d)][d] ) def _Bmin(self, b, Lt, Rt): S, i = self._B[b], b * self._size; return self._index[ i + self._D[S][Lt][Rt] ] def LCA(self, u, v): ut, vt, s = self._visit[u], self._visit[v], self._size; Lt, Rt = (ut, vt) if ut <= vt else (vt, ut); Lb, Li, Rb, Ri = Lt // s, Lt % s, Rt // s, Rt % s; return self._Bmin(Lb, Li, Ri) & self._mask if Lb == Rb else min(self._Tmin(Lb + 1, Rb), self._Bmin(Lb, Li, s - 1), self._Bmin(Rb, 0, Ri)) & self._mask #入力受取 N = int(input()) G = [[] for _ in range(N)] for _ in range(N - 1): u,v = map(int,input().split()) G[u - 1].append(v - 1) G[v - 1].append(u - 1) #LCAの前計算 LCA = Linear_LCA(N, G) #クエリを実行 imos配列をAに記録しておく A = [0] * (N + 1) for _ in range(int(input())): a,b = map(int,input().split()) a,b = a-1, b-1 L = LCA.LCA(a,b) A[a] += 1 A[b] += 1 A[L] -= 1 A[LCA.parent[L]] -= 1 #rootの場合はA[-1]に反映される #BFS帰りがけ順にクエリを消化 ans = 0 Q = [(0, -1)] for now,back in Q: for nxt in G[now]: if nxt != back: Q.append((nxt, now)) while Q: now,back = Q.pop() ans += A[now] * (A[now] + 1) // 2 A[back] += A[now] #答えを出力 print(ans)