#include using namespace std; #define rep(i,a,b) for(int i=a;i> &g; public: struct Node { int vid; int head; int parent; int heavy; int length; }; vector nodes; HeavyLightDecomposition(const vector> &g) : g(g), nodes(g.size()) { dfs(0, -1); bfs(0); } void forEach(int u, int v, function f) { while (true) { if (nodes[u].vid > nodes[v].vid) { swap(u, v); } int h = nodes[v].head; int l = nodes[h].length; if (nodes[u].head == nodes[v].head) { f(nodes[h].vid, l, nodes[u].vid, nodes[v].vid); break; } else { f(nodes[h].vid, l, nodes[h].vid, nodes[v].vid); v = nodes[h].parent; } } } int operator[](int k) { return nodes[k].vid; } private: int dfs(int curr, int prev) { nodes[curr].heavy = -1; nodes[curr].parent = prev; int maxSub = 0; int sub = 1; for (int next : g[curr]) { if (next == prev) { continue; } int subNext = dfs(next, curr); sub += subNext; if (maxSub < subNext) { maxSub = subNext; nodes[curr].heavy = next; } } return sub; } void bfs(int s) { queue q; q.push(s); int k = 0; while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = nodes[i].heavy) { nodes[i].vid = k++; nodes[i].head = h; nodes[h].length++; for (int j : g[i]) { if (j != nodes[i].parent && j != nodes[i].heavy) { q.push(j); } } } } } }; typedef long long ll; template struct LazySegTreeAddSum { vector a, b; explicit LazySegTreeAddSum() { a.resize(2 * NV - 1); b.resize(2 * NV - 1); } void add(int i, int il, int ir, int l, int r, int z) { if (l <= il and ir <= r) { a[i] += z; b[i] += z * (ir - il); } else if (ir <= l or r <= il) { } else { add(2 * i + 1, il, (il + ir) / 2, l, r, z); add(2 * i + 2, (il + ir) / 2, ir, l, r, z); b[i] = a[i] * (ir - il) + b[2 * i + 1] + b[2 * i + 2]; } } ll get(int i, int il, int ir, int l, int r) { if (l <= il and ir <= r) return b[i]; else if (ir <= l or r <= il) return 0; else return a[i] * (min(ir, r) - max(il, l)) + get(2 * i + 1, il, (il + ir) / 2, l, r) + get(2 * i + 2, (il + ir) / 2, ir, l, r); } void add(int l, int r, int z) { add(0, 0, NV, l, r, z); } // [l,r)に+z ll get(int l, int r) { return get(0, 0, NV, l, r); } // [l,r)の総和 }; int N, Q; vector> G; LazySegTreeAddSum<1<<20> sst; //----------------------------------------------------------------------------------- int main() { cin >> N; G.resize(N); rep(i, 0, N - 1) { int a, b; scanf("%d%d", &a, &b); a--; b--; G[a].push_back(b); G[b].push_back(a); } HeavyLightDecomposition hld(G); sst.add(0, N, 1); ll ans = 0; cin >> Q; rep(q, 0, Q) { int a, b; scanf("%d%d", &a, &b); a--; b--; hld.forEach(a, b, [&](int head, int len, int l, int r) { //printf("<%d : %lld>\n", hld[l] + 1, sst.get(l, l + 1)); ans += sst.get(l, r + 1); sst.add(l, r + 1, 1); }); } printf("%lld\n", ans); }