#include using namespace std; double elapsed() { static clock_t curr; clock_t prev = curr; curr = clock(); return (double)(curr - prev) / CLOCKS_PER_SEC * 1000; } class HLDecomposition { public: HLDecomposition(int n) : g(n), vid(n), sub(n, 1), head(n), heavy(n, -1), parent(n) { } void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build() { dfs(0, -1); bfs(); } struct Iterator { int u, v; HLDecomposition *hl; Iterator(HLDecomposition *hl, int u, int v) : hl(hl), u(u), v(v) {} pair operator*() { if (hl->vid[u] > hl->vid[v]) swap(u, v); int l = max(hl->vid[hl->head[v]], hl->vid[u]); int r = hl->vid[v]; v = hl->head[u] != hl->head[v] ? hl->parent[hl->head[v]] : -1; return make_pair(l, r); } void operator++() {} bool operator!=(Iterator &) { return v != -1; } }; struct Enumerator { int u, v; HLDecomposition *hl; Enumerator(HLDecomposition *hl, int u, int v) : hl(hl), u(u), v(v) {} Iterator begin() const { return Iterator(hl, u, v); } Iterator end() const { return Iterator(hl, u, v); } }; Enumerator enumerate(int u, int v) { return Enumerator(this, u, v); } private: vector> g; vector vid; vector sub; vector head; vector heavy; vector parent; void dfs(int curr, int prev) { parent[curr] = prev; for (int next : g[curr]) if (next != prev) { dfs(next, curr); sub[curr] += sub[next]; if (heavy[curr] == -1 || sub[heavy[curr]] < sub[next]) { heavy[curr] = next; } } } void bfs() { int k = 0; queue q; q.push(0); while (!q.empty()) { int first = q.front(); q.pop(); for (int curr = first; curr != -1; curr = heavy[curr]) { vid[curr] = k++; head[curr] = first; for (int next : g[curr]) { if (next == parent[curr]) continue; if (next == heavy[curr]) continue; q.push(next); } } } } }; struct BIT { vector bit; BIT(int n) : bit(n) {} void update(int k, long long v) { k++; while (k < bit.size()) { bit[k] += v; k += k & -k; } } long long query(int k) { k++; long long res = 0; while (k > 0) { res += bit[k]; k -= k & -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; HLDecomposition hl(n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); hl.add(u - 1, v - 1); } 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--; for (auto lr : hl.enumerate(u, v)) { res += rsq.query(lr.first, lr.second); } for (auto lr : hl.enumerate(u, v)) { rsq.update(lr.first, lr.second, 1); } } cout << res << endl; }