#include #include #include using namespace std; using UnWeightedGraph = vector>; struct LowestCommonAncestor { const UnWeightedGraph &g; int root; vector> parent; // parent[k][v] := 2^k-th parent of v vector depth; LowestCommonAncestor(const UnWeightedGraph &g, int r = 0) : \ g(g), root(r), depth(g.size()) { } void build() { int V = g.size(); int h = 1; while ((1 << h) < V) ++h; // 32 - __builtin_clz(V) parent.assign(h, vector(V, -1)); dfs(root, -1, 0); for (int k = 0; k + 1 < h; ++k) for (int v = 0; v < V; ++v) { if (parent[k][v] != -1) parent[k + 1][v] = parent[k][parent[k][v]]; } } void dfs(int u, int p, int d) { parent[0][u] = p; depth[u] = d; for (auto v: g[u]) if (v != p) dfs(v, u, d + 1); } int get(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < parent.size(); ++k) { if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v]; } if (u == v) return u; for (int k = parent.size() - 1; k >= 0; --k) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - depth[get(u, v)] * 2; } }; vector sum; void rec(const UnWeightedGraph &g, int u, int p) { for (auto v: g[u]) if (v != p) { rec(g, v, u); sum[u] += sum[v]; } } int main() { int N; cin >> N; UnWeightedGraph g(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--, v--; g[u].emplace_back(v); g[v].emplace_back(u); } LowestCommonAncestor lca(g); lca.build(); sum.resize(N + 1); int Q; cin >> Q; while (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]--; } rec(g, 0, -1); long long res = 0; for (int v = 0; v < N; v++) res += 1LL * sum[v] * (sum[v] + 1) / 2; cout << res << endl; return 0; }