#include using namespace std; using ll = long long; class heavy_light_decomposition { const int n; vector> g; vector par, head, in, out; void dfs1(int rt) { vector size(n, 1); vector iter(n); vector> stp; stp.reserve(n); stp.emplace_back(rt, -1); while (!stp.empty()) { int v = stp.back().first; if (iter[v] < g[v].size()) { if (g[v][iter[v]] != stp.back().second) stp.emplace_back(g[v][iter[v]], v); ++iter[v]; continue; } par[v] = stp.back().second; for (auto& u : g[v]) if (u == par[v]) { if (u != g[v].back()) swap(u, g[v].back()); g[v].pop_back(); break; } for (auto& u : g[v]) { size[v] += size[u]; if (size[u] > size[g[v].front()]) swap(u, g[v].front()); } stp.pop_back(); } } void dfs2(int rt) { int it = 0; vector iter(n); vector st; st.reserve(n); st.push_back(rt); while (!st.empty()) { int v = st.back(); if (!iter[v]) in[v] = it++; if (iter[v] < g[v].size()) { int u = g[v][iter[v]]; head[u] = iter[v] ? u : head[v]; st.push_back(u); ++iter[v]; continue; } out[v] = it; st.pop_back(); } } public: heavy_light_decomposition(int n_) : n(n_), g(n), par(n), head(n), in(n), out(n) {} heavy_light_decomposition(const vector>& G) : n(G.size()), g(G), par(n), head(n), in(n), out(n) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { dfs1(rt); head[rt] = rt; dfs2(rt); } void path_query(int u, int v, function f) { while (true) { if (in[u] > in[v]) swap(u, v); f(max(in[head[v]], in[u]), in[v] + 1); if (head[u] == head[v]) return; v = par[head[v]]; } } }; template class fenwick_tree { const int n; vector data; public: fenwick_tree(int n_) : n(n_), data(n) {} T find(int p) const { T res = 0; while (p >= 0) { res += data[p]; p = (p & (p + 1)) - 1; } return res; } void add(int p, T val) { while (p < n) { data[p] += val; p |= p + 1; } } }; template class range_add_range_sum { const int n; fenwick_tree bit0, bit1; public: range_add_range_sum(int n_) : n(n_), bit0(n), bit1(n) {} T find(int p) const { return bit1.find(p) * (p + 1) + bit0.find(p); } T find(int l, int r) const { return find(r - 1) - find(l - 1); } void add(int l, int r, T val) { bit0.add(l, -val * l); bit1.add(l, val); bit0.add(r, val * r); bit1.add(r, -val); } }; int main() { ios::sync_with_stdio(false), cin.tie(0); ll N, Q, A, B; cin >> N; heavy_light_decomposition hl(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--, v--; hl.add_edge(u, v); } hl.build(); range_add_range_sum ra(N); cin >> Q; ll res = 0; while (Q--) { cin >> A >> B; A--; B--; hl.path_query(A, B, [&](int l, int r) { res += ra.find(l, r) + (r - l); }); hl.path_query(A, B, [&](int l, int r) { ra.add(l, r, 1); }); } cout << res << endl; return 0; }