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)) paths.append((self.par[u]+1,self.par[u]+2)) return paths 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) #print(HLD.order) """ #セグ木に乗せる例(距離) #セグ木の初期化 if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さwを持たせる l[HLD.order[a]] = w else:#それの逆 l[HLD.order[b]] = w seg = Segtree(l,0,f) #aが親で、a-b間の辺の重さをxに変更 if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さxを持たせる l[HLD.order[a]] = x else:#それの逆 l[HLD.order[b]] = x #u~vの間の距離の和 for e_u,e_v in HLD.decomposition(u,v):#分解した区間ごとに足す ans += seg.query(e_u,e_v) """ data0 = [0]*(N+1) data1 = [0]*(N+1) # 区間[l, r)に x を加算 def _add(data, k, x): while k <= N: data[k] += x k += k & -k def add(l, r, x): _add(data0, l, -x*(l-1)) _add(data0, r, x*(r-1)) _add(data1, l, x) _add(data1, r, -x) # 区間[l, r)の和を求める def _get(data, k): s = 0 while k: s += data[k] k -= k & -k return s def query(l, r): return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1) Q = int(input()) ans = 0 for i in range(Q): a,b = map(int, input().split()) a-=1;b-=1 for j,k in HLD.decomposition(a,b): add(j+1,k+1,1) #print(HLD.decomposition(a,b)) for i in range(1,N+1): tmp = query(i,i+1) ans += (1+tmp) * tmp //2 print(ans)