#include using namespace std; #define int long long #define rep(i,n) for(int i=0;i #define mod (int)(1e9+7) #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") template inline void chmin(T &a, T b) { a = min(a, b); } template inline void chmax(T &a, T b) { a = max(a, b); } //RAQ-RSQ struct Segtree{ vectordat,lazy; int size=1; Segtree(int x){ while(size1){ lazy[k*2+1]+=lazy[k]; lazy[k*2+2]+=lazy[k]; } lazy[k]=0; } void update(int a,int b,int x,int k=0,int l=0,int r=-1){ if(r==-1)r=size; eval(k,l,r); if(r<=a||b<=l)return; if(a<=l&&r<=b){ lazy[k]+=x; eval(k,l,r); return; } update(a,b,x,k*2+1,l,(l+r)/2); update(a,b,x,k*2+2,(l+r)/2,r); dat[k]=dat[k*2+1]+dat[k*2+2]; } int query(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=size; eval(k,l,r); if(r<=a||b<=l)return 0; if(a<=l&&r<=b){ return dat[k]; } int lv=query(a,b,k*2+1,l,(l+r)/2); int rv=query(a,b,k*2+2,(l+r)/2,r); return lv+rv; } }; struct HeavyLightDecomposition{ struct heavy_set{ vectorelement; int depth,parent; heavy_set(int v,int d,int par):element(1,v),depth(d),parent(par){} }; vector>G; vectorS; vectorsubtree_size,set_index,ele_index; int subtree(int v,int par){ int &sz=subtree_size[v]; if(sz>0)return sz; sz=1; for(int i:G[v])if(i!=par)sz+=subtree(i,v); return sz; } void make_path(int v,int par,int id){ set_index[v]=id; ele_index[v]=S[id].element.size()-1; int mxindex,mx=0; for(int i:G[v])if(i!=par){ if(mx>&G,int root=0):G(G){ init(root); } P get(int v){ return {set_index[v],ele_index[v]}; } }; signed main() { int N; cin>>N; vector>G(N); rep(i,N-1){ int u,v;cin>>u>>v;u--;v--; G[u].push_back(v);G[v].push_back(u); } HeavyLightDecomposition hld(G); vectorsegtree; rep(i,hld.S.size())segtree.emplace_back(hld.S[i].element.size()); int ans=0; int Q;cin>>Q; while(Q--){ int u,v;cin>>u>>v;u--;v--; if(hld.S[hld.get(v).first].depthhld.S[hld.get(u).first].depth){ P tmp=hld.get(v); segtree[tmp.first].update(0,tmp.second+1,1); ans+=segtree[tmp.first].query(0,tmp.second+1); v=hld.S[tmp.first].parent; } while(hld.get(v).first!=hld.get(u).first){ P tmp=hld.get(v),tmp2=hld.get(u); segtree[tmp.first].update(0,tmp.second+1,1); ans+=segtree[tmp.first].query(0,tmp.second+1); v=hld.S[tmp.first].parent; segtree[tmp2.first].update(0,tmp2.second+1,1); ans+=segtree[tmp2.first].query(0,tmp2.second+1); u=hld.S[tmp2.first].parent; } P tu=hld.get(u),tv=hld.get(v); int mn=min(tu.second,tv.second),mx=max(tu.second,tv.second); segtree[tu.first].update(mn,mx+1,1); ans+=segtree[tu.first].query(mn,mx+1); } cout<