#include using namespace std; #define Min(x) *min_element(x.begin(),x.end()) #define Max(x) *max_element(x.begin(),x.end()) #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define range(i,a,b,c) for(int i=a;i<(int)(b);i+=c) using ll = long long; using ch = char; using str = string; using vll = vector; using vch = vector; using vvll = vector; using sll = set; const ll mod998 = 998244353; const ll mod107 = 1e9+7; const ll using_mod = mod998; vll erat(2e6,-1); vll mobius(2e6,1); void comp_erat(){ erat[1] = 1; for(int i=2;i<2e6;i++){ if(erat[i]==-1){ for(int j=i;j<2e6;j+=i){ if(j%(i*i)==0) mobius[j] = 0; else mobius[j] *= -1; if(erat[j]==-1) erat[j] = i; } } } } template vector fast_zeta(vector &f){ int len_f = f.size(); vector F = f; for(int i=2;i0;j--){ F[j] += F[j*i]; } } } return F; } template vector fast_mobius(vector &F){ int len_F = F.size(); vector f = F; for(int i=2;i>i & 1){ re = (re*amari[i])%mod; } } return re; } ll inv(ll a,ll m=using_mod) { ll b = m, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } ll nCr(const ll &n,const ll &r,const ll &mod=using_mod){ if (n < r) return 0; ll one = fact_mod[n]; ll two = (fact_mod[n-r]*fact_mod[r])%mod; ll re = (one*inv(two,mod))%mod; return re; } ll _GCM(ll n,ll m){ if(m>n) swap(n,m); if(m == 0){ return n; } else{ return _GCM(m,n%m); } } ll GCM(ll n,ll m){ if(n<0) n*=-1; if(m<0) m*=-1; return _GCM(n,m); } vll ruiseki(const vll &a){ vll re(a.size()+1); for(int i=0;i<(int)a.size();i++){ re[i+1] = re[i]+a[i]; } return re; } ll bisect_left(const vll &s,const ll &a){ auto itr = lower_bound(s.begin(), s.end(), a); ll re = itr - s.begin(); return re; } ll bisect_right(const vll &s,const ll &a){ auto itr = lower_bound(s.begin(), s.end(), a+1); ll re = itr - s.begin(); return re; } void print(vector s){ cout << '['; for(int i:s){ cout << i << ' '; } cout << ']'; cout << endl; } void print(vector> s){ cout << '['; for(pair i:s){ cout << '{' << i.first << ' ' << i.second << '}' << ' '; } cout << ']'; cout << endl; } struct HLD{ int n; vector> tree; vector childs_num; vector parents; vector vertex; vector id; vector head; vector depth; //部分木サイズを計算 void comp_childs_num(int node){ int now = 0; for(int nei:tree[node]){ comp_childs_num(nei); now += childs_num[nei]; } childs_num[node] = now + 1; } //heavy child優先のdfs void dfs(int node,int now_head){ head[node] = now_head; vertex.push_back(node); pair maxi(-1,-1); for(int nei:tree[node]){ maxi = max(maxi,{childs_num[nei],nei}); } int heavy_child = maxi.second; if(heavy_child != -1){ int heavy_child = maxi.second; dfs(heavy_child,now_head); for(int nei:tree[node]){ if(nei!=heavy_child){ dfs(nei,nei); } } } } //コンストラクタ HLD(int _n,vector> s){ n = _n; tree.assign(n,vector(0)); id.assign(n,0); head.assign(n,0); depth.assign(n,0); parents.assign(n,-1); childs_num.assign(n,-1); vector> graph(n,vector(0)); for(pair i : s){ graph[i.first].push_back(i.second); graph[i.second].push_back(i.first); } //根付き木の構築 //depth.parentsをついでに計算 deque queue; queue.push_back(0); vector visited(n,false); visited[0] = true; while(!queue.empty()){ int now = queue.front();queue.pop_front(); for(int nei:graph[now]){ if(!visited[nei]){ depth[nei] = depth[now] + 1; parents[nei] = now; tree[now].push_back(nei); visited[nei] = true; queue.push_back(nei); } } } //部分木サイズを計算 comp_childs_num(0); //heavy_child優先のdfs //head,vertexを計算 dfs(0,0); //idを計算 for(int i=0;i to_path(){ return vertex; } vector> use_path(int u,int v){ vector> re; while(true){ if(head[u] == head[v]){ re.push_back({min(id[u],id[v]) ,max(id[u],id[v]) + 1}); return re; } if(id[u] < id[v]){ re.push_back({min(id[v],id[head[v]]) ,max(id[v],id[head[v]]) + 1}); v = parents[head[v]]; } else{ re.push_back({min(id[u],id[head[u]]) ,max(id[u],id[head[u]]) + 1}); u = parents[head[u]]; } } } }; using S = pair; using F = int; S op(S a,S b){ S re = {a.first+b.first,a.second+b.second}; return re; } S e(){ return {0,0}; } S mapping(F a,S b){ b.first += b.second * a; return b; } F composition(F a,F b){ return a+b; } F id(){ return 0; } template struct LazySegTree{ int _n,size,log_; vector data; vector lazy; LazySegTree(int num){ log_ = 0; size = 1; while(size < num){ log_ ++; size *= 2; } data.assign(2*size, e()); lazy.assign(2*size, id()); } void push(int num){ data[num] = mapping(lazy[num],data[num]); if(num < size){ lazy[num*2] = composition(lazy[num],lazy[num*2]); lazy[num*2+1] = composition(lazy[num],lazy[num*2+1]); } lazy[num] = id(); } void push_up(int num){ if(num < size){ data[num] = op(data[num*2],data[num*2+1]); } } void set(int num,S s) { num += size; for(int i=log_;i >= 1;i--) push(num >> i); data[num] = s; for(int i=1;i <= log_;i++) push_up(num >> i); } S _prod(int nl,int nr,int gl,int gr,int node){ push(node); if(nr <= gl || gr <= nl) return e(); else if(gl <= nl && nr <= gr){ return data[node]; } else{ int mid = (nl+nr) / 2; S re = op(_prod(nl,mid,gl,gr,node*2),_prod(mid,nr,gl,gr,node*2+1)); push_up(node); return re; } } S prod(int l,int r){ return _prod(0,size,l,r,1); } void _apply(int nl,int nr,int gl,int gr,int node,F f){ push(node); if(nr <= gl || gr <= nl){} else if(gl <= nl && nr <= gr){ lazy[node] = f; push(node); } else{ int mid = (nl+nr) / 2; _apply(nl,mid,gl,gr,node*2,f);_apply(mid,nr,gl,gr,node*2+1,f); push_up(node); } } void apply(int l,int r,F f){ _apply(0,size,l,r,1,f); } }; int main(){ int n;cin >> n; vector> edgs; rep(i,n-1){ int a,b;cin >> a >> b;a--;b--; edgs.push_back({a,b}); } HLD hld(n,edgs); LazySegTree seg(n); rep(i,n){ seg.set(i,{1,1}); } int q;cin >> q; ll ans = 0; rep(i,q){ int a,b;cin >> a >> b;a--;b--; for(pair j:hld.use_path(a,b)){ pair now = seg.prod(j.first,j.second); ans += now.first; seg.apply(j.first,j.second,1); } } cout << ans << endl; }