#include using namespace std; class HLDecomposition { public: HLDecomposition(int n) : g(n), vid(n), sub(n, 1), head(n), heavy(n, -1), parent(n) { } void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); } 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); } int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; return lca(u, parent[head[v]]); } vector parent; private: vector> g; vector vid; vector sub; vector head; vector heavy; 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; 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; }