#include using namespace std; struct HLDecomposition { const vector> &g; vector vid, head, heavy, parent; vector light_depth; vector> light_parent; HLDecomposition(vector> &g) : g(g), vid(g.size()), head(g.size()), heavy(g.size(), -1), parent(g.size()), light_depth(g.size()), light_parent(5, vector(g.size())) { dfs(0, -1); bfs(); for (int i = 0; i < g.size(); i++) { light_parent[0][i] = parent[head[i]]; } for (int i = 0; i < 4; i++) { for (int j = 0; j < g.size(); j++) { if (light_parent[i][j] != -1) { light_parent[i + 1][j] = light_parent[i][light_parent[i][j]]; } else { light_parent[i + 1][j] = -1; } } } } int lca(int u, int v) { if (light_depth[u] < light_depth[v]) swap(u, v); for (int i = 4; i >= 0; i--) { if (light_depth[u] - light_depth[v] >= 1 << i) { u = light_parent[i][u]; } } for (int i = 4; i >= 0; i--) { if (light_parent[i][u] != light_parent[i][v]) { u = light_parent[i][u]; v = light_parent[i][v]; } } if (head[u] == head[v]) { return vid[u] < vid[v] ? u : v; } else { return light_parent[0][u]; } } int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0; for (int next : g[curr]) if (next != prev) { int s = dfs(next, curr); sub += s; if (max_sub < s) max_sub = s, heavy[curr] = next; } return sub; } void bfs() { int k = 0; queue q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { light_depth[i] = light_depth[h]; vid[i] = k++; head[i] = h; for (int j : g[i]) if (j != parent[i] && j != heavy[i]) { light_depth[j] = light_depth[i] + 1; q.push(j); } } } } }; vector> g; 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; g.resize(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); } HLDecomposition hl(g); 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; }