#include using namespace std; #define _p(...) (void)printf(__VA_ARGS__) #define forr(x,arr) for(auto&& x:arr) #define _overload3(_1,_2,_3,name,...) name #define _rep2(i,n) _rep3(i,0,n) #define _rep3(i,a,b) for(int i=int(a);i=int(a);i--) #define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__) #define ALL(x) (x).begin(), (x).end() #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) #define fst first #define snd second typedef vector vi;typedef vector vvi;typedef pair pii;typedef vector vpii; typedef long long ll; struct LCA { int H, W; int V; vector > parent; vector depth; // LCA(木の頂点数) LCA(vector >& E) : W(E.size()), depth(E.size()) { H = 1; while (1 << H < W) H++; parent.resize(H, vector(W)); // 適当な頂点からdfsして親を求めておく dfs(E, 0, -1, 0); // 親をダブリングする for (int k = 1; k < H; k++) { for (int v = 0; v < W; v++) { parent[k][v] = parent[k-1][v] == -1 ? -1 : parent[k-1][parent[k-1][v]]; } } } void dfs(vector >& E, int cur, int par, int dep) { parent[0][cur] = par; depth[cur] = dep; for (int i = 0; i < (int) E[cur].size(); i++) { if (E[cur][i] != par) dfs(E, E[cur][i], cur, dep + 1); } } // u と v の LCA を求める int query(int u, int v) { // 深い方を v にしておく if (depth[u] > depth[v]) swap(u, v); // 根からの深さが u と同じになるまで v の親をたどる for (int k = 0; k < H; k++) { if ((depth[v]-depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; // 二分探索でLCAを求める for (int k = H - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } }; void Main() { int N; scanf("%d", &N); vvi E(N); rep(i, N-1) { int u, v; scanf("%d%d", &u, &v); u--; v--; E[u].push_back(v); E[v].push_back(u); } LCA lca(E); vi &par = lca.parent[0]; vector C(N); int Q; scanf("%d", &Q); while (Q--) { int a, b; scanf("%d%d", &a, &b); a--; b--; int l = lca.query(a, b); int p = par[l]; C[a]++; C[b]++; C[l]--; if (p >= 0) C[p]--; } function dfs = [&](int cur) { forr(nex, E[cur]) if (nex != par[cur]) { dfs(nex); C[cur] += C[nex]; } }; dfs(0); ll ans = 0; rep(i, N) ans += C[i] * (C[i]+1) / 2; _p("%lld\n", ans); } int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }