#include using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair Pii; typedef tuple TUPLE; typedef vector V; typedef vector VV; typedef vector VVV; typedef vector> Graph; const int inf = 1e9; const int mod = 1e9 + 7; class LCA { private: static const int MAX_LOG = 20; const int n; Graph G; V depth; VV par; V cnt; // 各頂点を通った回数 public: LCA(int _n) : n(_n), G(_n), par(MAX_LOG, V(_n)), depth(_n), cnt(_n) {} // undirected void addEdge(int a, int b) { G[a].emplace_back(b); G[b].emplace_back(a); } // 各頂点の深さと、1つ前の親を求める void dfs(int v, int p, int d) { // cerr << v << " " << p << " " << d << endl; par[0][v] = p; depth[v] = d; for (auto nxt : G[v]) { if (nxt != p) { dfs(nxt, v, d + 1); } } } // 各頂点の2^k番目の親を求めておく void setPar() { // 0を根として1つ目の親を求める dfs(0, -1, 0); // 2^i番目の親を求める rep(i, MAX_LOG - 1) { rep(j, n) { if (par[i][j] == -1) { par[i + 1][j] = -1; } else { par[i + 1][j] = par[i][par[i][j]]; } } } } int lca(int a, int b) { // まずaとbの深さを揃える if (depth[a] > depth[b]) { swap(a, b); } rep(i, MAX_LOG) { if ((depth[b] - depth[a]) >> i & 1) { b = par[i][b]; } } if (a == b) return a; // ぶつかる直前までa, bを上げる rrep(i, MAX_LOG) { if (par[i][a] != par[i][b]) { a = par[i][a]; b = par[i][b]; } } // aとbの1つ前の親は一致している return par[0][a]; } void updateCnt(int u, int v) { cnt[u]++; cnt[v]++; int w = lca(u, v); cnt[w]--; if (par[0][w] != -1) cnt[par[0][w]]--; } int imosFinal(int v, int p) { int t = 0; for (auto&& nxt : G[v]) { if (nxt != p) t += imosFinal(nxt, v); } cnt[v] += t; return cnt[v]; } int answer() { imosFinal(0, -1); int ans = 0; for (auto&& x : cnt) { ans += (x + 1) * x / 2; } return ans; } }; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int N; cin >> N; LCA lca(N); rep(i, N - 1) { int u, v; cin >> u >> v; u--, v--; lca.addEdge(u, v); } lca.setPar(); int Q; cin >> Q; rep(i, Q) { int u, v; cin >> u >> v; u--, v--; lca.updateCnt(u, v); } cout << lca.answer() << endl; }