from collections import * from itertools import * from functools import * from heapq import * import sys,math input = sys.stdin.buffer.readline class HLD(): ### HL分解をしてIDを振りなおしたものに対して、パスに含まれる区間を返す ### SegTreeにのせる配列はIDを並び替えたもの def __init__(self,e,root=0): self.N = len(e) self.e = e par = [-1]*N sub = [-1]*N self.root = root dist = [-1]*N v = deque() dist[root]=0 v.append(root) while v: x = v.popleft() for ix in e[x]: if dist[ix] !=-1: continue dist[ix] = dist[x] + 1 v.append(ix) H = [(-dist[i],i) for i in range(N)] H.sort() for h,i in H: tmp = 1 for ix in e[i]: if sub[ix] == -1: par[i]= ix else: tmp += sub[ix] sub[i] = tmp self.ID = [-1]*N self.ID[self.root]=0 self.HEAD = [-1]*N head = [-1]*N self.PAR = [-1]*N visited = [False]*N self.HEAD[0]=0 head[self.root]=0 depth = [-1]*N depth[self.root]=0 self.DEPTH = [-1]*N self.DEPTH[0]=0 cnt = 0 v = deque([self.root]) self.SUB = [0]*N self.SUB[0] = N while v: x = v.popleft() visited[x]=True self.ID[x]=cnt cnt += 1 n = len(self.e[x]) tmp = [(sub[ix],ix) for ix in self.e[x]] tmp.sort() flg = 0 if x==self.root: flg -= 1 for _,ix in tmp: flg += 1 if visited[ix]: continue v.appendleft(ix) if flg==n-1: head[ix] = head[x] depth[ix] = depth[x] else: head[ix] = ix depth[ix] = depth[x]+1 for i in range(self.N): self.PAR[self.ID[i]] = self.ID[par[i]] self.HEAD[self.ID[i]] = self.ID[head[i]] self.DEPTH[self.ID[i]] = depth[i] self.SUB[self.ID[i]] = sub[i] def path_query(self,l,r): L = self.ID[l] R = self.ID[r] res = [] if self.DEPTH[L]R: L,R = R,L tmp = (L,R+1) res.append(tmp) return res def sub_query(self,k): K = self.ID[k] return (K,K+self.SUB[K]) class RSQandRAQ(): """区間加算、区間取得クエリをそれぞれO(logN)で答える add: 区間[l, r)にvalを加える query: 区間[l, r)の和を求める l, rは0-indexed """ def __init__(self, n): self.n = n self.bit0 = [0] * (n + 1) self.bit1 = [0] * (n + 1) def _add(self, bit, i, val): i = i + 1 while i <= self.n: bit[i] += val i += i & -i def _get(self, bit, i): s = 0 while i > 0: s += bit[i] i -= i & -i return s def add(self, l, r, val): """区間[l, r)にvalを加える""" self._add(self.bit0, l, -val * l) self._add(self.bit0, r, val * r) self._add(self.bit1, l, val) self._add(self.bit1, r, -val) def query(self, l, r): """区間[l, r)の和を求める""" return self._get(self.bit0, r) + r * self._get(self.bit1, r) \ - self._get(self.bit0, l) - l * self._get(self.bit1, l) N = int(input()) e = [[] for _ in range(N)] for _ in range(N-1): u,v = map(int,input().split()) u -= 1 v -= 1 e[u].append(v) e[v].append(u) Q = int(input()) ans = 0 hld = HLD(e) ID = hld.ID[:] T = RSQandRAQ(N) for _ in range(Q): a,b = map(int,input().split()) a -= 1 b -= 1 for l,r in hld.path_query(a,b): ans += T.query(l,r) ans += r-l T.add(l,r,1) print(ans)