#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); } struct Tree{ int root,N; vector>G,doubling; vectordepth; Tree(int x,int r){ N=x;G.resize(N);root=r; doubling.resize(20); rep(i,20)doubling[i].resize(N); depth.resize(N,-1);depth[root]=0; } void unite(int x,int y){ G[x].push_back(y);G[y].push_back(x); } void dfs(int x){ for(int i:G[x]){ if(depth[i]==-1){ depth[i]=depth[x]+1; doubling[0][i]=x; dfs(i); } } } void init(){ dfs(root); rep(i,19){ rep(j,N){ if(doubling[i][j]==-1)doubling[i+1][j]=-1; else doubling[i+1][j]=doubling[i][doubling[i][j]]; } } } int lca(int x,int y){ if(depth[x]>depth[y])swap(x,y); rep(i,20){ if((depth[y]-depth[x])>>i&1){ y=doubling[i][y]; } } if(x==y)return x; for(int i=19;i>=0;i--){ if(doubling[i][x]!=doubling[i][y]){ x=doubling[i][x];y=doubling[i][y]; } } return doubling[0][x]; } }; //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); } 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 parent; heavy_set(int v,int par):element(1,v),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; 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); Tree tree(N,0); rep(i,N-1){ int u,v;cin>>u>>v;u--;v--; G[u].push_back(v);G[v].push_back(u); tree.unite(u,v); } tree.init(); 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--; int lca=tree.lca(u,v); while(hld.get(v).first!=hld.get(lca).first){ 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(u).first!=hld.get(lca).first){ P tmp=hld.get(u); segtree[tmp.first].update(0,tmp.second+1,1); ans+=segtree[tmp.first].query(0,tmp.second+1); u=hld.S[tmp.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<