#include using namespace std; using lint = long long; template using V = vector; template using VV = V< V >; template struct FenwickTree { const int n; V t; FenwickTree(int n) : n(n), t(n + 1) {} void add(int i, T x) { for (++i; i <= n; i += i & -i) t[i] += x; } T sum(int i) const { T s = 0; for (; i; i -= i & -i) s += t[i]; return s; } }; template struct AddSumTree { const int n; FenwickTree d, e; AddSumTree(int n) : n(n), d(n), e(n) {} void add(int l, int r, T x) { d.add(l, x), e.add(l, l * x); if (r < n) d.add(r, -x), e.add(r, -r * x); } T sum(int i) const { return i * d.sum(i) - e.sum(i); } T sum(int l, int r) const { return sum(r) - sum(l); } }; using Tree = AddSumTree; struct HeavyLightDecomposition { const bool edge; const int n; VV<> g; V<> sz, par, in, out, anc, rev; HeavyLightDecomposition(VV<>& g, bool edge, int r = 0) : edge(edge), n(g.size()), g(g), sz(n), par(n), in(n), out(n), anc(n), rev(n) { dfs_sz(r, -1); anc[r] = r; dfs_hl(r); } void dfs_sz(int v, int p) { par[v] = p; for (auto&& w : g[v]) if (w == p) { swap(w, g[v].back()); g[v].pop_back(); break; } sz[v] = 1; for (auto&& w : g[v]) { dfs_sz(w, v); sz[v] += sz[w]; if (sz[w] > sz[g[v][0]]) swap(w, g[v][0]); } } void dfs_hl(int v) { static int t = 0; in[v] = t++; rev[in[v]] = v; for (int w : g[v]) { anc[w] = w == g[v][0] ? anc[v] : w; dfs_hl(w); } out[v] = t; } int lca(int u, int v) const { while (true) { if (in[u] > in[v]) swap(u, v); if (anc[u] == anc[v]) return u; v = par[anc[v]]; } } lint acc(Tree& t, int u, int v) const { lint res = 0; while (true) { if (in[u] > in[v]) swap(u, v); if (anc[u] == anc[v]) break; res += t.sum(in[anc[v]], in[v] + 1); v = par[anc[v]]; } res += t.sum(in[u] + edge, in[v] + 1); return res; } void act(Tree& t, int u, int v, int f) const { while (true) { if (in[u] > in[v]) swap(u, v); if (anc[u] == anc[v]) break; t.add(in[anc[v]], in[v] + 1, f); v = par[anc[v]]; } t.add(in[u] + edge, in[v] + 1, f); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; VV<> g(n); for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v, --u, --v; g[u].push_back(v); g[v].push_back(u); } HeavyLightDecomposition hld(g, false); Tree t(n); t.add(0, n, 1); int q; cin >> q; lint res = 0; while (q--) { int u, v; cin >> u >> v, --u, --v; res += hld.acc(t, u, v); hld.act(t, u, v, 1); } cout << res << '\n'; }