#include #include #include using namespace std; struct LowestCommonAncestor { const vector> &g; int root, h; vector> par; // par[k][v] := 2^k-th parent of v vector dep, ord; LowestCommonAncestor(const vector> &g, int r = 0) : \ g(g), root(r), dep(g.size()), ord(g.size()) { build(); } void build() { int V = g.size(), id = 0; h = 1; while ((1 << h) < V) ++h; // 32 - __builtin_clz(V) par.assign(h, vector(V, -1)); dfs(root, -1, 0, id); for (int k = 0; k + 1 < h; ++k) for (int v = 0; v < V; ++v) { if (par[k][v] != -1) par[k + 1][v] = par[k][par[k][v]]; } } void dfs(int u, int p, int d, int &id) { par[0][u] = p; dep[u] = d; ord[u] = id++; for (auto v: g[u]) if (v != p) dfs(v, u, d + 1, id); } int get(int u, int v) { if (dep[u] > dep[v]) swap(u, v); for (int k = 0; k < h; ++k) { if ((dep[v] - dep[u]) >> k & 1) v = par[k][v]; } if (u == v) return u; for (int k = h - 1; k >= 0; --k) { if (par[k][u] != par[k][v]) u = par[k][u], v = par[k][v]; } return par[0][u]; } int ancestor(int u, int k) { for (int i = h - 1; i >= 0; i--) if (k >> i & 1) u = par[i][u]; return u; } int dist(int u, int v) { return dep[u] + dep[v] - dep[get(u, v)] * 2; } }; vector> g; vector imos; void dfs(int u, int p) { for (int v: g[u]) if (v != p) { dfs(v, u); imos[u] += imos[v]; } } int main() { int n; cin >> n; g.resize(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); imos.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.par[0][p]; if (pp == -1) pp = n; imos[a]++, imos[p]--; imos[b]++, imos[pp]--; } dfs(0, -1); long long sum = 0; for (int i = 0; i < n; i++) sum += imos[i] * (imos[i] + 1) / 2; cout << sum << endl; return 0; }