#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b vid head, heavy, parent : unknown // depth : id -> depth inv : vid -> id struct HLDecomposition { vector> g; vector vid, head, heavy, parent, depth, inv, in, out; HLDecomposition() {} HLDecomposition(int n) { init(n); } void init(int n) { g.resize(n); vid.resize(n, -1); head.resize(n); heavy.resize(n, -1); parent.resize(n); depth.resize(n); inv.resize(n); in.resize(n); out.resize(n); } void add(int u, int v) { g[u].insert(v); g[v].insert(u); } void build() { dfs(0, -1); dfs_hld(); } 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; } int t = 0; void dfs_hld(int v = 0) { vid[v] = in[v] = t; t++; inv[in[v]] = v; for (auto u : g[v]) if(depth[v] < depth[u]) { head[u] = (u == heavy[v] ? head[v] : u); dfs_hld(u); } out[v] = t; } 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); } } } void foreach(int u, int v, function f) { // [x,y] if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) foreach(u, parent[head[v]], f); } int ancestor(int from, int times) { while (true) { if (depth[head[from]] > depth[from] - times) { times -= depth[from] - depth[head[from]] + 1; if (head[from] == 0)return -1; from = parent[head[from]]; } else return inv[vid[from] - times]; } } 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]]); } int distance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } int child(int parent, int child, int times) { assert(depth[parent] struct LazySegTree { // [L,R) #define def 0 #define ldef 0 V comp(V l, V r) { return l + r; } void setLazy(int i, V v) { lazy[i] += v; } void push(int k, int l, int r) { dat[k] += lazy[k] * (r - l); if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); } lazy[k] = ldef; } vector dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); } void update(int a, int b, V v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); } else { update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r); dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]); } } V get(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return def; if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2); auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y); } void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); } V get(int a, int b) { return get(a, b, 0, 0, NV); } void debug() { printf("[OH]\n"); rep(i, 0, 32) printf("%d ", get(i, i + 1)); printf("\n"); /* set que; rep(i, 0, 32) que.insert(i + NV - 1); printf("[dat]\n"); while (1 < que.size()) { set ne; for (int i : que) { printf("%d ", dat[i]); ne.insert(i / 2); } printf("\n"); for (int i : que) { printf("%d ", i); ne.insert(i / 2); } printf("\n"); swap(que, ne); } printf("[lazy]\n"); que.clear(); rep(i, 0, 32) que.insert(i + NV); while (1 < que.size()) { set ne; for (int i : que) { printf("%d ", lazy[i]); ne.insert(i / 2); } printf("\n"); swap(que, ne); }*/ } }; /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ ll ans = 0; LazySegTree st; //--------------------------------------------------------------------------------------------------- void _main() { int N; cin >> N; HLDecomposition hld(N); rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; hld.add(a, b); } hld.build(); st.update(0, N, 1); int Q; cin >> Q; rep(q, 0, Q) { int a, b; cin >> a >> b; a--; b--; hld.foreach(a, b, [](int x, int y) { ans += st.get(x, y + 1); st.update(x, y + 1, 1); }); } cout << ans << endl; }