#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define X first #define Y second #define pb push_back #define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X)) #define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X)) #define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X)) #define repe(X,Y) for ((X) = 0;(X) < (Y);++(X)) #define peat(X,Y) for (;(X) < (Y);++(X)) #define all(X) (X).begin(),(X).end() #define rall(X) (X).rbegin(),(X).rend() #define eb emplace_back #define UNIQUE(X) (X).erase(unique(all(X)),(X).end()) using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; template using vv=vector>; template ostream& operator<<(ostream &os, const vector &t) { os<<"{"; rep(i,t.size()) {os< ostream& operator<<(ostream &os, const pair &t) { return os<<"("< inline bool MX(T &l,const T &r){return l inline bool MN(T &l,const T &r){return l>r?l=r,1:0;} const ll MOD=1e9+7; //doubling typedef vv Graph; class Lca{ public: vector dep,cld; vv par; const int LOGN=20; void dfs(const Graph &g,int root){ int n=g.size(); vector vst(n); stack st; st.push(root); while(!st.empty()){ int v=st.top(); st.pop(); if(vst[v]==1){ vst[v]=2; rep(i,g[v].size())if(g[v][i]!=par[v][0]) cld[v]+=cld[g[v][i]]+1; }else if(vst[v]==0){ st.push(v); vst[v]=1; rep(i,g[v].size())if(!vst[g[v][i]]){ dep[g[v][i]]=dep[v]+1; par[g[v][i]][0]=v; st.push(g[v][i]); } } } } Lca(const Graph &g){ int n=g.size(); par.resize(n,vector(LOGN,-1)); dep.resize(n); cld.resize(n); dfs(g,0); rep(i,LOGN-1)rep(v,n) par[v][i+1]=par[v][i]<0?-1:par[par[v][i]][i]; } int anc(int v,int n){ rep(i,LOGN)if(n>>i&1) if((v=par[v][i])<0)break; return v; } int LCA(int v,int w){ if(dep[v]>dep[w]) swap(v,w); w=anc(w,dep[w]-dep[v]); rrep(i,LOGN) if(par[v][i]!=par[w][i]){ v=par[v][i]; w=par[w][i]; } return v==w?v:par[v][0]; } int dist(int v,int w){return dep[v]+dep[w]-2*dep[LCA(v,w)];} }; ll ret=0; ll dfs(vv &g,int v,int p,vector &val){ ll re=val[v]; for(int w:g[v]) if(w!=p) re+=dfs(g,w,v,val); ret+=re*(re+1)/2; //cout<>n; vv g(n); int x,y; rep(i,n-1){ cin>>x>>y; --x; --y; g[x].pb(y); g[y].pb(x); } Lca h(g); int q; cin>>q; vector v(n); while(q--){ cin>>x>>y; --x; --y; int p=h.LCA(x,y); --v[p]; if(p){ --v[h.par[p][0]]; } ++v[x]; ++v[y]; } dfs(g,0,-1,v); cout<