#include using namespace std; 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(int u, int v, HLDecomposition *hl) : u(u), v(v), hl(hl) {} 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 + 1); } void operator++() {} bool operator !=(Iterator &) { return v != -1; } }; struct Enumerator { int u, v; HLDecomposition *hl; Enumerator(HLDecomposition *hl, int u, int v) : u(u), v(v), hl(hl) {} Iterator begin() const { return Iterator(u, v, hl); } Iterator end() const { return Iterator(u, v, hl); } }; 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] && next != heavy[curr]) { q.push(next); } } } } }; const int N = 1 << 17; long long seg[N * 2]; long long lazy[N * 2]; void push(int k, int l, int r) { seg[k] += lazy[k] * (r - l); if (r - l > 1) { lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } void update(int a, int b, long long v, int k = 0, int l = 0, int r = N) { push(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = v; push(k, l, r); return; } update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2]; } long long query(int a, int b, int k = 0, int l = 0, int r = N) { push(k, l, r); if (r <= a || b <= l) return 0; if (a <= l && r <= b) return seg[k]; return query(a, b, k * 2 + 1, l, (l + r) / 2) + query(a, b, k * 2 + 2, (l + r) / 2, r); } 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(); update(0, n, 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 += query(lr.first, lr.second); } for (auto lr : hl.enumerate(u, v)) { update(lr.first, lr.second, 1); } } cout << res << endl; }