#include #include using namespace std; typedef vector > Graph; struct LCA { vector > parent; // parent[d][v] := 2^d-th parent of v vector depth; LCA() { } LCA(const Graph &G, int r = 0) { init(G, r); } void init(const Graph &G, int r = 0) { int V = (int)G.size(); int h = 1; while ((1<(V, -1)); depth.assign(V, -1); dfs(G, r, -1, 0); for (int i = 0; i+1 < (int)parent.size(); ++i) for (int v = 0; v < V; ++v) if (parent[i][v] != -1) parent[i+1][v] = parent[i][parent[i][v]]; } void dfs(const Graph &G, int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1); } int get(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int i = 0; i < (int)parent.size(); ++i) if ( (depth[v] - depth[u]) & (1<= 0; --i) { if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } } return parent[0][u]; } }; vector sum; void rec(const Graph &G, int v, int p) { for (auto e : G[v]) { if (e == p) continue; rec(G, e, v); sum[v] += sum[e]; } } int main() { int N, Q; cin >> N; Graph G(N); for (int i = 0; i < N-1; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; G[u].push_back(v); G[v].push_back(u); } LCA lca(G); cin >> Q; sum.assign(N+1, 0); for (int q = 0; q < Q; ++q) { int a, b; cin >> a >> b; --a, --b; int p = lca.get(a, b); int pp = lca.parent[0][p]; if (pp == -1) pp = N; sum[a]++; sum[pp]--; sum[b]++; sum[p]--; //cout << a << ", " << b << ": " << p << endl; } rec(G, 0, -1); long long res = 0; for (int v = 0; v < N; ++v) res += sum[v] * (sum[v] + 1) / 2; cout << res << endl; }