#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i ) #define rep(i,n) REP(i,0,n) typedef long long ll; typedef pair pint; typedef pair pli; const int inf=1e9+7; const ll longinf=1LL<<60 ; const ll mod=1e9+7 ; int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1} ; struct BIT{ private: int sz; vector node; public: BIT(int n):sz(n),node(n+1){}; void add(int k,ll x){ k++; while(k<=sz){ node[k]+=x; k+=k&-k; } } ll sum(int k){ k++; ll ret=0; while(k>0){ ret+=node[k]; k-=k&-k; } return ret; } ll sum(int l,int r){ return sum(r-1)-sum(l-1); } ll get(int k){ return sum(k,k+1); } }; BIT bit(101010); struct HLDecomposition{ int n,pos; vector> v; vector idx,head,sz,hvy,par,depth,inv,type; HLDecomposition(){}; HLDecomposition(int s): n(s),pos(0),v(n),idx(n,-1),head(n),sz(n,1), hvy(n,-1),par(n),depth(n),inv(n),type(n){} void addedge(int x,int y){ v[x].push_back(y); v[y].push_back(x); } void dfs1(int rt){ par[rt]=-1; depth[rt]=0; stack st; st.push({rt,0}); while(!st.empty()){ int x=st.top().first; int& i=st.top().second; if(i<(int)v[x].size()){ int to=v[x][i++]; if(to==par[x])continue; par[to]=x; depth[to]=depth[x]+1; st.push({to,0}); } else { st.pop(); int res=0; for(int to:v[x]){ if(to==par[x])continue; sz[x]+=sz[to]; if(sz[to]>res)res=sz[to],hvy[x]=to; } } } } void dfs2(int r,int c){ int &k=pos; stack st; st.push(r); while(!st.empty()){ int h=st.top();st.pop(); for(int x=h;x!=-1;x=hvy[x]){ type[x]=c; head[x]=h; idx[x]=k++; inv[idx[x]]=x; for(int to:v[x]) if(to!=par[x]&&to!=hvy[x])st.push(to); } } } void build(vector rs=vector(1,0)){ int c=0; for(int r:rs){ dfs1(r); dfs2(r,c++); } } void f(int x,int y){ //ここに何か書く!!! bit.add(x,1); bit.add(y+1,-1); } void for_v(int x,int y){ while(1){ if(idx[x]>idx[y])swap(x,y); f(max(idx[head[y]],idx[x]),idx[y]); if(head[x]!=head[y])y=par[head[y]]; else break; } } void for_edge(int x,int y){ while(1){ if(idx[x]>idx[y])swap(x,y); if(head[x]!=head[y]){ f(idx[head[y]],idx[y]); y=par[head[y]]; } else{ if(x!=y)f(idx[x]+1,idx[y]); break; } } } int lca(int x,int y){ while(1){ if(idx[x]>idx[y])swap(x,y); if(head[x]==head[y])return x; y=par[head[y]]; } } int dist(int x,int y){ return depth[x]+depth[y]-2*depth[lca(x,y)]; } }; int main(){ int n;cin>>n; HLDecomposition hl(n); rep(i,n-1){ int x,y; scanf("%d%d",&x,&y); hl.addedge(x-1, y-1); } hl.build(); int q;cin>>q; rep(i,q){ int x,y; scanf("%d%d",&x,&y); hl.for_v(x-1,y-1); } ll ans=0; rep(i,n){ ll ret=bit.sum(i); ans+=ret*(ret+1)/2; } cout<