import sys sys.setrecursionlimit(2*10**5) class HeavyLightDecomposition:#N,edge def __init__(self,n,edge): self.n=n self.size=[1]*n self.par=[-1]*n que=[0] while que:#親とこの数を数える段階 v=que.pop() if v>=0:#向かう点が0以上なら木を下る、0未満なら木を登る、下る際には今見ている辺の上向き、下向きを準備して親を定義する for u in edge[v]: if u!=self.par[v]: que.append(~u) que.append(u) self.par[u]=v else:#上向きではこの数を伝搬する v=~v self.size[self.par[v]]+=self.size[v] self.head=[-1]*n#heavy辺上なら連結しているなかで一番上に位置する点 self.head[0]=0 self.order=[-1]*n#振り直された番号 self.heavy_child=[-1]*n#自分とheavy辺を張られた子 que=[0] cnt=0 while que: v=que.pop() self.order[v]=cnt cnt+=1 mx=0 for u in edge[v]:#heavy辺を決める if u!=self.par[v] and mxself.order[v]: u,v=v,u if self.head[u]!=self.head[v]:#自分を含むheavy辺が同じ paths.append((self.order[self.head[v]],self.order[v]+1)) v=self.par[self.head[v]] else: paths.append((self.order[u]+1,self.order[v]+1)) tmp = self.lca(u,v) # print("aaaa",tmp,self.head[u]) paths.append((tmp,tmp+1)) return paths def lca(self,u,v):#u,v 0-indexedでu,vのlcaを返す while True: if self.order[u]>self.order[v]: u,v=v,u if self.head[u]==self.head[v]: return u v = self.par[self.head[v]] N = int(input()) edge = [[] for i in range(N)] for i in range(N-1): u,v = map(int, input().split()) u-=1;v-=1 edge[u].append(v) edge[v].append(u) HLD = HeavyLightDecomposition(N,edge) Q = int(input()) visited = [-1]*N dp = [0]*N ans = 0 for i in range(Q): a,b = map(int, input().split()) a-=1;b-=1 dp[a] += 1 dp[b] += 1 tmp = HLD.lca(a,b) dp[tmp]-=1 if HLD.par[tmp] != -1: dp[HLD.par[tmp]]-=1 #print(dp) visited[0] = 1 ans = 0 def dfs(now): global ans #print(now) for _next in edge[now]: if visited[_next] == -1: visited[_next] = 1 dfs(_next) dp[now] += dp[_next] ans += (dp[now]+1) * dp[now] //2 dfs(0) print(ans)