/* -*- coding: utf-8 -*- * * 399.cc: No.399 動的な領主 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int BN = 17; /* typedef */ typedef long long ll; typedef vector vi; typedef queue qi; struct Stat { int i, p, d; Stat() {} Stat(int _i, int _p, int _d): i(_i), p(_p), d(_d) {} }; /* global variables */ vi nbrs[MAX_N]; int ds[MAX_N], prts[MAX_N][BN], cns[MAX_N], ts[MAX_N]; /* subroutines */ /* main */ int main() { int n; cin >> n; for (int i = 0; i < n - 1; i++) { int ai, bi; cin >> ai >> bi; ai--, bi--; nbrs[ai].push_back(bi); nbrs[bi].push_back(ai); } ds[0] = 0; prts[0][0] = -1; cns[0] = nbrs[0].size(); queue q; q.push(Stat(0, -1, 0)); while (! q.empty()) { Stat u = q.front(); q.pop(); vi &nbru = nbrs[u.i]; int vd = u.d + 1; for (vi::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int &vi = *vit; if (vi != u.p) { ds[vi] = vd; prts[vi][0] = u.i; cns[vi] = nbrs[vi].size() - 1; q.push(Stat(vi, u.i, vd)); } } } for (int i = 1; i < BN; i++) for (int j = 0; j < n; j++) { int &p = prts[j][i - 1]; prts[j][i] = (p < 0) ? -1 : prts[p][i - 1]; } int m; cin >> m; while (m--) { int ai, bi; cin >> ai >> bi; ai--, bi--; int u = ai, v = bi; if (ds[u] > ds[v]) swap(u, v); for (int i = BN - 1; i >= 0; i--) if (((ds[v] - ds[u]) >> i) & 1) v = prts[v][i]; if (u != v) { for (int i = BN - 1; i >= 0; i--) if (prts[u][i] != prts[v][i]) u = prts[u][i], v = prts[v][i]; u = prts[u][0]; } ts[ai]++; ts[bi]++; ts[u]--; if (prts[u][0] >= 0) ts[prts[u][0]]--; } qi qq; for (int i = 0; i < n; i++) if (cns[i] == 0) qq.push(i); while (! qq.empty()) { int u = qq.front(); qq.pop(); int v = prts[u][0]; if (v >= 0) { ts[v] += ts[u]; if (--cns[v] == 0) qq.push(v); } } //for (int i = 0; i < n; i++) printf("%d ", ts[i]); putchar('\n'); ll sum = 0; for (int i = 0; i < n; i++) { ll t = ts[i]; sum += t * (t + 1) / 2; } printf("%lld\n", sum); return 0; }