#include using namespace std; using ll = long long; class heavy_light_decomposition { const int n; vector> g; vector in, out, size, head, par, dep, inv; int it; void erase_par(int v, int prev) { par[v] = prev; for (auto& u : g[v]) { if (u == g[v].back()) break; if (u == prev) swap(u, g[v].back()); erase_par(u, v); } g[v].pop_back(); } void dfs1(int v) { for (auto& u : g[v]) { dfs1(u); size[v] += size[u]; if (size[u] > size[g[v][0]]) swap(u, g[v][0]); } } void dfs2(int v) { in[v] = it++; inv[in[v]] = v; for (auto u : g[v]) { head[u] = (u == g[v][0] ? head[v] : u); dep[u] = dep[v] + (u != g[v][0]); dfs2(u); } out[v] = it; } public: heavy_light_decomposition(int n_) : n(n_), g(n), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), dep(n), inv(n), it(0) {} heavy_light_decomposition(const vector>& G) : n(G.size()), g(G), in(n, -1), out(n, -1), size(n, 1), head(n), par(n, -1), dep(n), inv(n), it(0) {} void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { for (auto v : g[rt]) erase_par(v, rt); 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(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; }