#include using namespace std; vector g[101010]; namespace HL { const int N = 1e5 + 10; int vid[N]; int head[N]; int parent[N]; int heavy[N]; int sub[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() { 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); } } const int N = 1 << 17; long long sum[N * 2]; long long lazy[N * 2]; void push(int k, int w) { if (lazy[k] == 0) return; sum[k] += lazy[k] * w; if (w > 1) { lazy[k * 2 + 0] += lazy[k]; lazy[k * 2 + 1] += lazy[k]; } lazy[k] = 0; } long long get_val(int k, int w) { return sum[k] + lazy[k] * w; } void update(int l, int r, long long v) { l += N; r += N; int L = l; int R = r; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) lazy[l++] += v; if (r & 1) lazy[--r] += v; } int w = 1; for (; L > 1; L >>= 1, R >>= 1) { sum[L >> 1] = get_val(L, w) + get_val(L ^ 1, w); sum[R >> 1] = get_val(R, w) + get_val(R ^ 1, w); w *= 2; } } long long query(int l, int r) { l += N; r += N; for (int i = 17; i >= 0; i--) { push(l >> i, 1 << i); push(r >> i, 1 << i); } long long res = 0; int w = 1; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) res += get_val(l++, w); if (r & 1) res += get_val(--r, w); w *= 2; } return res; } 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(); update(0, n, 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 += query(l, r + 1); }); HL::for_each(u, v, [&](int l, int r) { update(l, r + 1, 1); }); } cout << res << endl; }