#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]; } }; class UnionFindTree{ struct base_node{ int parent; int rank; int size; }; vector node; public: UnionFindTree(int n){ node.resize(n); for(int i=0; i node[y].rank){ node[y].parent = x; node[x].size += node[y].size; }else{ node[x].rank++; unite(x,y); } } }; int main(){ int n; cin >> n; assert(2<=n && n<=100000); UnionFindTree uft(n); vector> G(n+1); G[n].push_back(0); G[0].push_back(n); for(int i=0; i> u >> v; assert(1<=u && u<=n); assert(1<=v && v<=n); assert(u != v); u--; v--; G[u].push_back(v); G[v].push_back(u); uft.unite(u,v); } assert(uft.size(0) == n); LCA lca(G, n); vector> d(lca.get_max_depth()+1); for(int i=0; i sum(n+1, 0); int q; cin >> q; assert(1<=q && q<=100000); while(q--){ int u,v; cin >> u >> v; assert(1<=u && u<=n); assert(1<=v && v<=n); assert(u != v); u--; v--; int p = lca.get_lca(u,v); if(p == u || p == v){ if(u==p) swap(u,v); sum[u]++; sum[lca.get_parent(p)]--; }else{ sum[u]++; sum[v]++; sum[p]--; sum[lca.get_parent(p)]--; } } long long ans = 0; for(int i=d.size()-1; i>0; i--){ for(int v : d[i]){ ans += sum[v] * (sum[v]+1LL) / 2; sum[lca.get_parent(v)] += sum[v]; } } cout << ans << endl; return 0; }