#include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, l, r) for(ll i = l; i <= r; i++) static const int WH = 0; static const int GR = 1; static const int BL = 2; using namespace std; using ll = long long; using ull = unsigned long long; static const ll ll_INF = 1e18; static const ll MOD = 998244353; void chmin(ll &a, ll b) { a = min(a, b); } struct LCA { vector height; vector> anc; vector> linked; vector cnt; vector incr; int root; int vertex_num; LCA(int N, int root_vertex) { vertex_num = N; height = vector(N + 5, -1); anc = vector>(N + 5, vector(100, -1)); linked = vector>(N + 5); cnt = vector(N + 5, -1); incr = vector(N + 5, 0); root = root_vertex; } void add_edge(int u, int v) { linked[u].push_back(v); linked[v].push_back(u); } ll find_cnt(int u) { if(cnt[u] != -1) return cnt[u]; cnt[u] = 0; cnt[u] += incr[u]; for(int x:linked[u]){ if(x == find_anc(u,1)) continue; cnt[u] += find_cnt(x); } return cnt[u]; } void pass(int u, int v) { int ca = find_common_anc(u, v); incr[u]++; incr[v]++; incr[ca]--; if(ca != root) { incr[find_anc(ca, 1)]--; } } ll solve() { ll ans = 0; for(int i = 1; i <= vertex_num; i++) { ans += find_cnt(i) * (find_cnt(i) + 1) / 2; } return ans; } void find_height() { queue q; q.push(root); height[root] = 0; while(q.size()) { int nv = q.front(); q.pop(); for(int x : linked[nv]) { if(height[x] == -1) { height[x] = height[nv] + 1; q.push(x); anc[x][0] = nv; } } } } int find_anc_sub(int u, int p) { // 頂点uの2^p前の頂点を求める. // cout << "sub " << u << " " << p << " " << anc[u][p] << endl; if(anc[u][p] != -1) return anc[u][p]; if(height[u] < pow_ll(2, p)) return -1; anc[u][p] = find_anc_sub(find_anc_sub(u, p - 1), p - 1); return anc[u][p]; } int find_anc(int u, int dis) { int var = 1; int p = 0; while(dis) { if(dis & 1) u = find_anc_sub(u, p); p += 1; dis >>= 1; } return u; } int find_common_anc(int u, int v) { if(u == v) return u; int left = 0; int right = min(height[u], height[v]); while(right - left > 1) { int mid = (left + right) / 2; if(find_anc(u, height[u] - mid) == find_anc(v, height[v] - mid)) left = mid; else right = mid; } return find_anc(u, height[u] - left); } ll pow_ll(ll u, ll v) { // u^v ll ans = 1; while(v > 0) { if(v & 1) ans *= u; v >>= 1; u *= u; } return ans; } }; int main() { int N; cin >> N; LCA lca(N, 1); rep(i, 1, N - 1) { int u, v; cin >> u >> v; lca.add_edge(u, v); } lca.find_height(); int Q; cin >> Q; rep(i, 1, Q) { int a, b; cin >> a >> b; lca.pass(a, b); } //lca.find_cnt(); cout << lca.solve() << endl; return 0; }