#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define repeat(i, x) for (long long i = 0; (i) < (long long)(x); (i)++) #define rrepeat(i, x) for (long long i = (long long)((x) - 1); (i) >= 0; (i)--) #define traverse(it, ctn) for (auto it = (ctn).begin(); (it) != (ctn).end(); (it)++) #define rtraverse(it, ctn) for (auto it = (ctn).rbegin(); (it) != (ctn).rend(); (it)++) #define enumerate(i, a, b) for (long long i = (long long)(a); (i) < (long long)(b); (i)++) template void chmax(T& a1, T a2) { a1 = std::max(a1, a2); } template void chmin(T& a1, T a2) { a1 = std::min(a1, a2); } template ostream& operator<<(ostream& os, const pair& p) { return os << "(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const vector& v) { os << "["; for (int i = 0; i < v.size(); i++) os << (i == 0 ? "" : ", ") << v[i]; os << "]"; return os; } template ostream& operator << (ostream& os, map& mp) { os << "{"; for (auto it = mp.begin(); it != mp.end(); it++) { os << "(" << it->first << ": " << it->second << ")"; it++; if(it != mp.end()) os << ", "; it--; } os << "}"; return os; } template ostream& operator << (ostream& os, set& st) { os << "{"; for (auto it = st.begin(); it != st.end(); it++) { os << *it; ++it; if(it != st.end()) os << ", "; it--; } os << "}"; return os; } using int64 = long long; using Graph = std::vector>; class HLDecomposition { using Graph = std::vector>; const int N; const int root; const Graph T; std::vector> chains; std::vector depth; std::vector subsize; std::vector parent; std::vector chain_id; std::vector next; std::vector at; // 各頂点の深さと部分木のサイズを計算する void setup() { stack st; st.push(root); depth[root] = 0; while (not st.empty()) { int v = st.top(); st.pop(); if (v >= 0) { st.push(~v); for (int to : T[v]) { if (depth[to] >= 0) continue; st.push(to); parent[to] = v; depth[to] = depth[v] + 1; } } else { v = ~v; subsize[v] = 1; for (int to : T[v]) { if (parent[to] != v) continue; subsize[v] += subsize[to]; } } } } inline int head(int v) { return chains[chain_id[v]][0]; } inline int tail(int v) { return chains[chain_id[v]].back(); } inline int climb(int v) { return parent[head(v)]; } public: HLDecomposition(const Graph& t, int r) : N(std::distance(t.begin(), t.end())), root(r), T(t), chains(0), depth(N, -1), subsize(N, 0), parent(N, -1), chain_id(N, -1), next(N, -1), at(N, -1) {} void decompose() { setup(); queue Q; Q.push(root); while (not Q.empty()) { int v = Q.front(); Q.pop(); if (chain_id[v] < 0) { chains.push_back(std::vector()); chain_id[v] = chains.size() - 1; } int id = chain_id[v]; at[v] = chains[id].size(); chains[id].push_back(v); for (int to : T[v]) { if (parent[to] != v) continue; Q.push(to); if (next[v] < 0 or subsize[to] > subsize[next[v]]) { next[v] = to; } } if (next[v] >= 0) chain_id[next[v]] = id; } } int lca(int u, int v) { while (chain_id[u] != chain_id[v]) { if (depth[head(u)] > depth[head(v)]) u = climb(u); else v = climb(v); } return depth[u] > depth[v] ? v : u; } int get_parent(int v) { return parent[v]; } }; Graph T; vector cumsum; int64 dfs(int v, int par) { int64 res = 0; for (int to : T[v]) { if (to == par) continue; res += dfs(to, v); cumsum[v] += cumsum[to]; } res += cumsum[v] * (cumsum[v] + 1) / 2; return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; T.resize(N, vector()); cumsum.resize(N, 0); repeat (i, N - 1) { int u, v; cin >> u >> v; u--; v--; T[u].push_back(v); T[v].push_back(u); } HLDecomposition hl(T, 0); hl.decompose(); int Q; cin >> Q; repeat (i, Q) { int A, B; cin >> A >> B; A--; B--; cumsum[A]++; cumsum[B]++; int lca = hl.lca(A, B); cumsum[lca]--; if (hl.get_parent(lca) >= 0) cumsum[hl.get_parent(lca)]--; } cout << dfs(0, -1) << endl; return 0; }