#include using namespace std; #define rep(i,a,b) for(int i=a;i data; int seg_size; LazySegTreeAddSetSum(int n) { for (seg_size = 1; seg_size < n; seg_size *= 2); data.assign(seg_size * 2, Data()); } ll set(int a, int b, ll x, int l = 0, int r = -1, int k = 0) { if (r == -1) r = seg_size - 1; if (a <= l && r <= b) { data[k].set_data(x, 0); return data[k].calc_sum(l, r); } if (r < a || b < l) return data[k].calc_sum(l, r); if (data[k].valset) { data[k * 2 + 1].set_data(data[k].val, data[k].add); data[k * 2 + 2].set_data(data[k].val, data[k].add); } data[k].add = 0; data[k].valset = false; data[k].sum = set(a, b, x, l, (l + r) / 2, k * 2 + 1) + set(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2); return data[k].calc_sum(l, r); } ll add(int a, int b, ll x, int l = 0, int r = -1, int k = 0) { if (r == -1) r = seg_size - 1; if (a <= l && r <= b) { data[k].add += x; return data[k].calc_sum(l, r); } if (r < a || b < l) return 0; if (data[k].valset) { data[k * 2 + 1].set_data(data[k].val, 0); data[k * 2 + 2].set_data(data[k].val, 0); data[k].valset = false; } data[k].sum = add(a, b, x, l, (l + r) / 2, k * 2 + 1) + add(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2); return data[k].calc_sum(l, r); } ll query(int a, int b, int l = 0, int r = -1, int k = 0) { if (r == -1) r = seg_size - 1; if (r < a || b < l) return 0; if ((a <= l && r <= b) || data[k].valset) return data[k].calc_sum(max(a, l), min(b, r)); return query(a, b, l, (l + r) / 2, k * 2 + 1) + query(a, b, (l + r) / 2 + 1, r, k * 2 + 2) + data[k].add * (min(b, r) - max(a, l) + 1); } }; //----------------------------------------------------------------------------------- struct HLDecomposition { vector> 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)]; } }; //----------------------------------------------------------------------------------- int N; //----------------------------------------------------------------------------------- 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(); LazySegTreeAddSetSum st(N); st.add(0, N - 1, 1); int Q; cin >> Q; ll ans = 0; rep(q, 0, Q) { int a, b; scanf("%d%d", &a, &b); a--; b--; hld.for_each(a, b, [&](int u, int v) { ans += st.query(u, v); st.add(u, v, 1); }); } cout << ans << endl; }