#include #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; struct Graph { Graph(const int n) { edge.resize(n); } void addEdge(const int from, const int to) { edge[from].push_back(to); } vector> edge; }; template class SparseTable { public: using T = typename Base::T; using SemiLattice = Base; SparseTable(const vector& val) : size(val.size()), lg2(size + 1, 0) { for (int i = 2; i <= size; i++) { lg2[i] = lg2[i / 2] + 1; } table.resize(size, vector(lg2[size] + 1)); for (int i = 0; i < size; i++) { table[i][0] = val[i]; } for (int j = 0; j < lg2[size]; j++) { const int w = 1 << j; for (int i = 0; i <= size - (w << 1); i++) { T tl = table[i][j], tr = table[i + w][j]; table[i][j + 1] = op(tl, tr); } } } T accumulate(const int l, const int r) const { assert(0 <= l and l < r and r <= size); const int j = lg2[r - l]; return op(table[l][j], table[r - (1 << j)][j]); } private: const int size; vector lg2; vector> table; const SemiLattice op{}; }; struct Min { using T = pii; T operator()(const T& a, const T& b) const { return min(a, b); } }; void make_dfs(Graph& g, const Graph& g_, vector& used, vector& prev, const int s) { used[s] = true; for (const int to : g_.edge[s]) { if (not used[to]) { g.addEdge(s, to); prev[to] = s; make_dfs(g, g_, used, prev, to); } } } void make_dfs(const Graph& g, vector& nodes, vector& left, const int s, const int depth) { nodes.push_back(make_pair(depth, s)); left[s] = nodes.size() - 1; for (const int to : g.edge[s]) { make_dfs(g, nodes, left, to, depth + 1); nodes.push_back(make_pair(depth, s)); } } int acc_dfs(const Graph& g, vector& imos, const int s) { int sum = 0; for (const int to : g.edge[s]) { sum += acc_dfs(g, imos, to); } imos[s] += sum; return imos[s]; } int LCA(const SparseTable& stable, const vector& left, const int u, const int v) { const int l = left[u]; const int r = left[v]; return stable.accumulate(min(l, r), max(l, r) + 1).second; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; Graph g_(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--, v--; g_.addEdge(u, v); g_.addEdge(v, u); } Graph g(N); vector used(N, false); vector prev(N, -1); make_dfs(g, g_, used, prev, 0); vector nodes; vector left(N, 0); make_dfs(g, nodes, left, 0, 0); SparseTable stable(nodes); vector imos(N, 0); int Q; cin >> Q; for (int i = 0; i < Q; i++) { int a, b; cin >> a >> b; a--, b--; imos[a]++; imos[b]++; const int lca = LCA(stable, left, a, b); imos[lca]--; if (prev[lca] != -1) { imos[prev[lca]]--; } } acc_dfs(g, imos, 0); ll sum = 0; for (int i = 0; i < N; i++) { sum += (ll)imos[i] * ((ll)imos[i] + 1) / 2; } cout << sum << endl; return 0; }