#include #include #include #include #include using namespace std; class LCA{ int root; //depth of node[i] vector d; //parent of node[i] vector > p; int size; //initialization of depths and parents void init(vector > &g, int pos, int last, int v){ d[pos] = v; p[0][pos] = last; for(int i=0; i > //g[i][j] := node[i]'s edge gose to node[ g[i][j] ] LCA(vector > &g, int r){ int n = g.size(); root = r; d = vector(n); size = 1; while((1< >(size, vector(n)); init(g, root,-1,0); for(int k=0; k+1 < size; k++){ for(int v=0; v > &g){ int n = g.size(); root = 0; d = vector(n); size = 1; while((1< >(size, vector(n)); //initialize as root = 0 init(g, root,-1,0); for(int k=0; k+1 < size; k++){ for(int v=0; v d[v]) swap(u,v); for(int k=0; k> k & 1){ v = p[k][v]; } } if(u==v) return u; for(int k=size-1; k>=0; k--){ if(p[k][u] != p[k][v]) { u = p[k][u]; v = p[k][v]; } } return p[0][u]; } //return depth of node[u] int get_depth(int u){ return d[u]; } int get_max_depth(){ return *max_element(d.begin(), d.end()); } int get_parent(int u){ return p[0][u]; } }; int main(){ int n; cin >> n; vector> G(n+1); G[n].push_back(0); G[0].push_back(n); for(int i=0; i> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } LCA lca(G, n); long long ans = 0; vector num_visit(n+1, 0); int q; cin >> q; while(q--){ int u,v; cin >> u >> v; u--; v--; int p = lca.get_lca(u,v); if(p == u || p == v){ if(u==p) swap(u,v); while(1){ num_visit[u]++; ans += num_visit[u]; if(u == p) break; u = lca.get_parent(u); } }else{ while(1){ num_visit[u]++; ans += num_visit[u]; if(u == p) break; u = lca.get_parent(u); } while(1){ if(v == p) break; num_visit[v]++; ans += num_visit[v]; v = lca.get_parent(v); } } } cout << ans << endl; return 0; }