#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="< tree[100010]; class LCA { private: int n,ln; // number of nodes and log n public: vector > parent; vector depth; LCA(int _n) : n(_n), depth(_n){ ln=0; while(n>(1< >(ln, vector(n)); } void dfs(int v, int p, int d){ parent[0][v]=p; depth[v]=d; rep(i,tree[v].size()) if(tree[v][i]!=p) dfs(tree[v][i], v, d+1); } void init(int root){ dfs(root, -1, 0); for(int k=0; k+1 depth[v]) swap(u,v); for(int k=0; k>k & 1) v = parent[k][v]; } // now, depth[v] == depth[u] if(u==v) return u; for(int k=ln-1; k>=0; k--){ if(parent[k][u] != parent[k][v]){ u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; // END class LCA vector memo; // imos dfs, node n from f long imosTree(int n, int f){ long res=memo[n]; rep(i,tree[n].size()){ if(tree[n][i]!=f) res += imosTree(tree[n][i], n); } return memo[n]=res; } int main(){ int n, q; cin>>n; rep(i,n-1){ int u,v; scanf("%d %d", &u, &v); u--;v--; tree[u].pb(v); tree[v].pb(u); } LCA lca(n); lca.init(0); memo = vector(n, 0); cin>>q; rep(i,q){ int a,b; scanf("%d %d", &a, &b); a--;b--; int p = lca.query(a,b); memo[a]++; memo[b]++; memo[p]--; if(lca.parent[0][p]!=-1) memo[lca.parent[0][p]]--; } // imos in tree imosTree(0,-1); // calc result long res=0; rep(i,n) res += (long)memo[i]*(memo[i]+1)/2; cout<