#include using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #define all(x) x.begin(),x.end() /* */ #include #include #include #include #include using namespace std; struct Graph { struct edge { int to; }; int n; vector> edges; Graph(int N) { n = N; edges.resize(n, vector()); } int size() const { return n; } vector& operator[](int v) { return edges[v]; } }; struct Lca { int n; int log2_n; vector> parent; vector depth; Lca(Graph& g, int root) { n = g.size(); log2_n = floor(log2(n) + 2); parent.resize(log2_n, vector(n)); depth.resize(n); dfs(g, root, -1, 0); for (int k = 0; k + 1 < log2_n; k++) { for (int v = 0; v < n; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void dfs(Graph& g, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (auto& e : g[v]) { if (e.to != p) dfs(g, e.to, v, d + 1); } } int get(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < log2_n; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = log2_n - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; /* checked: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2723881#1 */ int N; i64 cnt[101010]; int main(){ cin >> N; Graph g(N + 1); rep(i,0,N - 2){ int u,v; cin >> u >> v; g[u].push_back({v}); g[v].push_back({u}); } Lca lca(g,1); int Q; cin >> Q; rep(i,0,Q - 1){ int A,B; cin >> A >> B; cnt[A]++; cnt[B]++; int p; cnt[p = lca.get(A,B)]--; if(lca.parent[0][p] != -1){ cnt[lca.parent[0][p]]--; } } vector> vec; rep(i,1,N){ vec.push_back({-lca.depth[i],i}); } sort(all(vec)); i64 ans = 0; for(auto p : vec){ int i = p.second; if(lca.parent[0][i] != -1){ cnt[lca.parent[0][i]] += cnt[i]; } ans += (cnt[i] + 1) * cnt[i] / 2; } cout << ans << endl; }