#include using namespace std; vector g[101010]; struct BIT { vector bit; void init(int n) { bit.resize(n + 1); } void update(int k, long long v) { for (k++; k < bit.size(); k += k & -k) { bit[k] += v; } } long long query(int k) { long long res = 0; for (k++; k > 0; k -= k & -k) { res += bit[k]; } return res; } }; struct RangeSumQuery { BIT bit0, bit1; void init(int n) { bit0.init(n); bit1.init(n); update(0, n - 1, 1); } // [a, b] void update(int a, int b, long long x) { bit0.update(a, -x * (a - 1)); bit1.update(a, x); bit0.update(b + 1, x * b); bit1.update(b + 1, -x); } // [0, a] long long query(int a) { return bit0.query(a) + bit1.query(a) * a; } // [a, b] long long query(int a, int b) { return query(b) - query(a - 1); } }; namespace HL { const int N = 1e5 + 10; int vid[N]; int head[N]; int parent[N]; int heavy[N]; int sub[N]; int depth[N]; RangeSumQuery rsq[N]; void dfs(int curr, int prev) { parent[curr] = prev; sub[curr] = 1; pair h(-1, -1); for (int next : g[curr]) { if (next == prev) continue; dfs(next, curr); sub[curr] += sub[next]; h = max(h, make_pair(sub[next], next)); } heavy[curr] = h.second; } void bfs() { queue q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); int k = 0; for (int i = h; i != -1; i = heavy[i]) { vid[i] = k++; head[i] = h; depth[i] = depth[h]; for (int j : g[i]) { if (j == parent[i]) continue; if (j == heavy[i]) continue; depth[j] = depth[i] + 1; q.push(j); } } rsq[h].init(k); } } void build() { dfs(0, -1); bfs(); } void for_each(int u, int v, function f) { if (head[u] != head[v]) { if (depth[u] > depth[v]) swap(u, v); f(head[v], 0, vid[v]); for_each(u, parent[head[v]], f); } else { if (vid[u] > vid[v]) swap(u, v); f(head[v], vid[u], vid[v]); } } } int main() { int n; cin >> n; for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); u--; v--; g[u].push_back(v); g[v].push_back(u); } HL::build(); int Q; cin >> Q; long long res = 0; while (Q--) { int u, v; scanf("%d %d", &u, &v); u--; v--; HL::for_each(u, v, [&](int h, int l, int r) { res += HL::rsq[h].query(l, r); }); HL::for_each(u, v, [&](int h, int l, int r) { HL::rsq[h].update(l, r, 1); }); } cout << res << endl; }