#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; template class EdgeBase { public: int to; T cost; EdgeBase(){}; EdgeBase(int to0, T cost0){to = to0; cost = cost0;} }; typedef EdgeBase Edge; template class LowestCommonAncestor { private: vector > to; // ダブリング先のノード vector depth; // 根からの深さ vector dist; // 根からの距離 public: int climb(int curr, int len) { int i = 0; while(len > 0){ if(len % 2 == 1) curr = to[curr][i]; len /= 2; ++ i; } return curr; } LowestCommonAncestor(const vector > >& edges, int root) { int n = edges.size(); to.assign(n, vector()); dist.assign(n, 0); depth.assign(n, 0); queue > q; q.push(make_pair(root, -1)); int cnt = 0; while(!q.empty()){ int m = q.size(); while(--m >= 0){ int curr, prev; tie(curr, prev) = q.front(); q.pop(); if(prev != -1){ to[curr].push_back(prev); int j = prev; for(unsigned k=0; k& e : edges[curr]){ if(e.to != prev){ depth[e.to] = depth[curr] + 1; dist[e.to] = dist[curr] + e.cost; q.push(make_pair(e.to, curr)); } } } ++ cnt; } } // 2つのノードの最小共通祖先を取得 int getAncestor(int a, int b) { int diff = depth[a] - depth[b]; if(diff < 0) b = climb(b, -diff); else a = climb(a, diff); if(a == b) return a; for(int i=to[a].size()-1; i>=0; --i){ if(i < (int)to[a].size() && to[a][i] != to[b][i]){ a = to[a][i]; b = to[b][i]; } } return to[a][0]; } // ノードの深さを取得 int getDepth(int a) { return depth[a]; } // 2つのノードの距離を取得 T getDist(int a, int b) { int c = getAncestor(a, b); return dist[a] + dist[b] - dist[c] * 2; } }; int main() { int n; cin >> n; vector > edges(n); for(int i=0; i> u >> v; -- u; -- v; edges[u].push_back(Edge(v, 1)); edges[v].push_back(Edge(u, 1)); } int root = 0; LowestCommonAncestor lca(edges, root); int query; cin >> query; vector cnt(n); while(--query >= 0){ int a, b; cin >> a >> b; -- a; -- b; ++ cnt[a]; ++ cnt[b]; int c = lca.getAncestor(a, b); -- cnt[c]; if(c != root){ int d = lca.climb(c, 1); -- cnt[d]; } } queue q; vector index; vector parent(n, -1); q.push(root); index.push_back(root); while(!q.empty()){ int curr = q.front(); q.pop(); for(const Edge& e : edges[curr]){ if(e.to != root && parent[e.to] == -1){ q.push(e.to); index.push_back(e.to); parent[e.to] = curr; } } } for(int i=n-1; i>0; --i) cnt[parent[index[i]]] += cnt[index[i]]; long long ans = 0; for(int i=0; i