#include using namespace std; typedef long long ll; struct chain { int l, r; bool d; chain(int left, int right, bool dir = false) : l(left), r(right), d(dir) {} }; class HLD { vector > G; vector vid, head, heavy, par, dep; int dfs(int v, int prev) { par[v] = prev; int cnt = 1, ma = 0; for (int i = 0; i < (int)G[v].size(); i++) { int to = G[v][i]; if (to != prev) { dep[to] = dep[v] + 1; int c = dfs(to, v); cnt += c; if (ma < c) { ma = c; heavy[v] = to; } } } return cnt; } public: HLD(int n) : G(n), vid(n, -1), head(n), heavy(n, -1), par(n), dep(n) {} void add(int u, int v) { G[u].push_back(v); G[v].push_back(u); } void build() { dfs(0, -1); int k = 0; queue q; q.push(0); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = heavy[i]) { vid[i] = k++; head[i] = h; for (int k = 0; k < (int)G[i].size(); k++) { int j = G[i][k]; if (j != par[i] && j != heavy[i]) q.push(j); } } } } int operator[](int v) { return vid[v]; } vector for_each(int u, int v) { vector res; while (true) { if (vid[u] > vid[v]) swap(u, v); res.push_back(chain(max(vid[head[v]], vid[u]), vid[v])); if (head[u] == head[v]) break; v = par[head[v]]; } return res; } vector for_each_directed(int u, int v) { vector res; while (true) { if (vid[u] > vid[v]) { res.push_back(chain(max(vid[head[u]], vid[v]), vid[u], true)); if (head[u] == head[v]) break; u = par[head[u]]; } else { res.push_back(chain(max(vid[head[v]], vid[u]), vid[v], false)); if (head[u] == head[v]) break; v = par[head[v]]; } } return res; } vector for_each_edge(int u, int v) { vector res; while (true) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { res.push_back(chain(vid[head[v]], vid[v])); v = par[head[v]]; } else { if (u != v) res.push_back(chain(vid[u] + 1, vid[v])); break; } } return res; } int lca(int u, int v) { while (true) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; template class LazySegmentTree { const int n; const T id; vector data, data2; int size(int n) { int res = 1; while (res < n) res <<= 1; return res; } T sub(int l, int r, int node, int lb, int ub) { if (ub <= l || r <= lb) return id; if (l <= lb && ub <= r) { return data[node] + data2[node] * (ub - lb); } return data2[node] * (min(r, ub) - max(l, lb)) + sub(l, r, node * 2, lb, (lb + ub) / 2) + sub(l, r, node * 2 + 1, (lb + ub) / 2, ub); } void suc(int l, int r, int node, int lb, int ub, T val) { if (ub <= l || r <= lb) return; if (l <= lb && ub <= r) { data2[node] += val; return; } data[node] += val * (min(r, ub) - max(l, lb)); suc(l, r, node * 2, lb, (lb + ub) / 2, val); suc(l, r, node * 2 + 1, (lb + ub) / 2, ub, val); } public: LazySegmentTree(int n_) : n(size(n_)), id(0), data(n * 2, id), data2(n * 2, id) {} void add(int l, int r, T val) { suc(l, r + 1, 1, 0, n, val); } T getSum(int l, int r) { return sub(l, r + 1, 1, 0, n); } }; int main() { ll N, Q, A, B; cin >> N; HLD hl(N); for (int i = 0, u, v; i < N - 1; i++) { cin >> u >> v; hl.add(u - 1, v - 1); } hl.build(); LazySegmentTree lst(N); cin >> Q; ll res = 0; while (Q--) { cin >> A >> B; A--; B--; vector chains = hl.for_each(A, B); for (int i = 0; i < (int)chains.size(); i++) { res += lst.getSum(chains[i].l, chains[i].r); } res += hl.distance(A, B) + 1; for (int i = 0; i < (int)chains.size(); i++) { lst.add(chains[i].l, chains[i].r, 1); } } cout << res << endl; return 0; }