import sys input = sys.stdin.readline sys.setrecursionlimit(10**5+10) class HLD: def __init__(self, N, G): self.G = G self.par = [-1]*N #親ノード self.size = [1]*N #部分木のサイズ self.depth = [-1]*N #深さ self.dfs1() self.in_order = [-1]*N #行きがけ順 self.in_order_now = 0 self.top = [-1]*N #分解後の連結成分の中で最も浅い頂点 self.dfs2() def dfs1(self): stack = [(0, -1, 0)] while stack: v, pv, d = stack.pop() self.depth[v] = d for nv in self.G[v]: if nv==pv: continue stack.append((nv, v, d+1)) self.par[nv] = v vs = [(self.depth[i], i) for i in range(N)] vs.sort(reverse=True) for _, v in vs: for nv in G[v]: if nv!=self.par[v]: self.size[v] += self.size[nv] def dfs2(self): stack = [(0, -1, 0)] while stack: v, pv, top_node = stack.pop() self.in_order[v] = self.in_order_now self.in_order_now += 1 self.top[v] = top_node if self.size[v]==1: continue M = 0 heavy_node = -1 for nv in self.G[v]: if nv==pv: continue if self.size[nv]>M: M = self.size[nv] heavy_node = nv for nv in self.G[v]: if nv==pv: continue if nv!=heavy_node: stack.append((nv, v, nv)) stack.append((heavy_node, v, top_node)) def query(self, u, v): res = [] while self.top[u]!=self.top[v]: if self.depth[self.top[u]]<=self.depth[self.top[v]]: res.append((self.in_order[self.top[v]], self.in_order[v])) v = self.par[self.top[v]] else: res.append((self.in_order[self.top[u]], self.in_order[u])) u = self.par[self.top[u]] res.append((min(self.in_order[u], self.in_order[v]), max(self.in_order[u], self.in_order[v]))) return res class BIT: def __init__(self, n): self.n = n self.bit = [0]*(n+1) def add(self, i, x): i += 1 while i<=self.n: self.bit[i] += x i += i&(-i) def acc(self, i): s = 0 while i>0: s += self.bit[i] i -= i&(-i) return s class RAQ_RSQ: def __init__(self, n): self.p = BIT(n) self.q = BIT(n) def add(self, s, t, x): self.p.add(s, -x*s) self.p.add(t, x*t) self.q.add(s, x) self.q.add(t, -x) def get_sum(self, s, t): return self.p.acc(t)+self.q.acc(t)*t-self.p.acc(s)-self.q.acc(s)*s 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) hdl = HLD(N, G) raq_rsq = RAQ_RSQ(N) Q = int(input()) ans = 0 for _ in range(Q): A, B = map(int, input().split()) for l, r in hdl.query(A-1, B-1): ans += raq_rsq.get_sum(l, r+1)+r-l+1 raq_rsq.add(l, r+1, 1) print(ans)