#include using namespace std; struct HLDecomposition { vector> g; vector vid; vector sub; vector head; vector heavy; vector parent; vector lca_depth; vector> lca_parent; HLDecomposition(int n) : g(n), vid(n), sub(n, 1), head(n), heavy(n, -1), parent(n), lca_depth(n), lca_parent(5, vector(n, -1)) { } void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); for (int i = 0; i < 4; i++) { for (int j = 0; j < g.size(); j++) { if (lca_parent[i][j] != -1) { lca_parent[i + 1][j] = lca_parent[i][lca_parent[i][j]]; } } } } int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; int U = u; u = head[u]; v = head[v]; for (int i = 4; i >= 0; i--) { if (lca_depth[v] - lca_depth[u] >= 1 << i) { int nv = lca_parent[i][v]; if (u != nv) v = nv; } } if (lca_parent[0][v] == u) { return vid[parent[v]] < vid[U] ? parent[v] : U; } for (int i = 4; i >= 0; i--) { if (lca_parent[i][u] != lca_parent[i][v]) { u = lca_parent[i][u]; v = lca_parent[i][v]; } } u = parent[u]; v = parent[v]; return vid[u] < vid[v] ? u : v; } struct Iterator { int u, v; HLDecomposition *hl; Iterator(HLDecomposition *hl, int u, int v) : hl(hl), u(u), v(v) {} pair operator*() { if (hl->vid[u] > hl->vid[v]) swap(u, v); int l = max(hl->vid[hl->head[v]], hl->vid[u]); int r = hl->vid[v]; v = hl->head[u] != hl->head[v] ? hl->parent[hl->head[v]] : -1; return make_pair(l, r + 1); } void operator++() {} bool operator!=(Iterator &) { return v != -1; } }; struct Enumerator { int u, v; HLDecomposition *hl; Enumerator(HLDecomposition *hl, int u, int v) : hl(hl), u(u), v(v) {} Iterator begin() const { return Iterator(hl, u, v); } Iterator end() const { return Iterator(hl, u, v); } }; Enumerator enumerate(int u, int v) { return Enumerator(this, u, v); } void dfs(int curr, int prev) { parent[curr] = prev; for (int next : g[curr]) if (next != prev) { dfs(next, curr); sub[curr] += sub[next]; if (heavy[curr] == -1 || sub[heavy[curr]] < sub[next]) { heavy[curr] = next; } } } void bfs() { int k = 0; queue q; q.push(0); while (!q.empty()) { int first = q.front(); q.pop(); for (int curr = first; curr != -1; curr = heavy[curr]) { vid[curr] = k++; head[curr] = first; for (int next : g[curr]) { if (next == parent[curr]) continue; if (next == heavy[curr]) continue; lca_depth[next] = lca_depth[first] + 1; lca_parent[0][next] = first; q.push(next); } } } } }; vector g[101010]; long long imos[101010]; long long ans; void dfs(int curr, int prev) { for (int next : g[curr]) if (next != prev) { dfs(next, curr); } if (prev != -1) { imos[prev] += imos[curr]; } ans += imos[curr] * (imos[curr] + 1) / 2; } int main() { int n; cin >> n; HLDecomposition hl(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); hl.add(u, v); } hl.build(); int Q; cin >> Q; while (Q--) { int u, v; scanf("%d %d", &u, &v); u--; v--; int l = hl.lca(u, v); imos[u]++; imos[v]++; imos[l]--; if (hl.parent[l] != -1) { imos[hl.parent[l]]--; } } dfs(0, -1); cout << ans << endl; }