#include using namespace std; #define rep(i,a,b) for(int i=a;i> g; // vid, head, heavy, parent は必須 // depth, inv は使用する機能によっては不要 vector vid, head, heavy, parent, depth, inv; HLDecomposition(int n) : g(n), vid(n, -1), head(n), heavy(n, -1), parent(n), depth(n), inv(n) {} // 辺 (u, v) を追加する void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } // 構築する void build() { dfs(0, -1); bfs(); } int dfs(int curr, int prev) { parent[curr] = prev; int sub = 1, max_sub = 0; for (int next : g[curr]) if (next != prev) { depth[next] = depth[curr] + 1; int sub_next = dfs(next, curr); sub += sub_next; if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; } return sub; } 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++; inv[vid[i]] = i; head[i] = h; for (int j : g[i]) if (j != parent[i] && j != heavy[i]) q.push(j); } } } // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! // 以下の関数は必要に応じて実装 // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! // 頂点属性の for_each 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); } // 頂点属性の for_each (有向 // fの3番目の引数には順方向なら0、逆方向なら1が渡される void for_each_directed(int u, int v, function f) { if (vid[u] > vid[v]) { f(max(vid[head[u]], vid[v]), vid[u], 1); if (head[u] != head[v]) for_each_directed(parent[head[u]], v, f); } else { f(max(vid[head[v]], vid[u]), vid[v], 0); if (head[u] != head[v]) for_each_directed(u, parent[head[v]], f); } } // 辺属性の for_each void for_each_edge(int u, int v, function f) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { f(vid[head[v]], vid[v]); for_each_edge(u, parent[head[v]], f); } else { if (u != v) f(vid[u] + 1, vid[v]); } } // 頂点 u の d 個上の頂点を求める(存在しないなら0を返す) int ancestor(int u, int d) { while (true) { if (depth[head[u]] > depth[u] - d) { d -= depth[u] - depth[head[u]] + 1; if (head[u] == 0) return 0; u = parent[head[u]]; } else { return inv[vid[u] - d]; } } } // 頂点 u と頂点 v の LCA を求める int lca(int u, int v) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; return lca(u, parent[head[v]]); } // 頂点 u と頂点 v の距離を求める int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } }; 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; LazySegTreeAddSum<1<<20> st; //----------------------------------------------------------------------------------- int main() { cin >> N; HLDecomposition hld(N); rep(i, 0, N - 1) { int a, b; scanf("%d%d", &a, &b); a--; b--; hld.add(a, b); } hld.build(); st.add(0, N, 1); ll ans = 0; cin >> Q; rep(q, 0, Q) { int a, b; scanf("%d%d", &a, &b); a--; b--; //printf("[%d %d] -> < ", a + 1, b + 1); hld.for_each(a, b, [&](int l, int r) { /*printf("[ "); rep(i, l, r + 1) printf("%d ", hld.vid[i] + 1); printf("] ");*/ ans += st.get(l, r + 1); st.add(l, r + 1, 1); }); //printf(">\n"); } printf("%lld\n", ans); }