#include using namespace std; vector g[101010]; namespace HL { int vid[101010]; int head[101010]; int parent[101010]; int heavy[101010]; int sub[101010]; void dfs(int curr, int prev) { parent[curr] = prev; sub[curr] = 1; vid[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, { sub[next], next }); } heavy[curr] = h.second; } void bfs() { int k = 0; queue q({ 0 }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { vid[i] = k++; head[i] = h; for (int j : g[i]) { if (j == parent[i]) continue; if (j == heavy[i]) continue; q.push(j); } } } } void build() { dfs(0, -1); bfs(); } void for_each(int u, int v, function f) { if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) for_each(u, parent[head[v]], f); } } struct BIT { vector bit; BIT(int n) : bit(n) {} 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; RangeSumQuery(int n) : bit0(n), bit1(n) {} // [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); } }; 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(); RangeSumQuery rsq(n + 10); rsq.update(0, n - 1, 1); 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 l, int r) { res += rsq.query(l, r); }); HL::for_each(u, v, [&](int l, int r) { rsq.update(l, r, 1); }); } cout << res << endl; }