#include #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define ALL(v) (v).begin(), (v).end() #define LLA(v) (v).rbegin(), (v).rend() #define SZ(v) (v).size() #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ read(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ read(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define STRING(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) using namespace std; using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template struct edge { int to; T cost; edge(int t, T c) : to(t), cost(c) {} }; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; template inline vector make_vec(size_t a, T val) { return vector(a, val); } template inline auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } void read() {} template inline void read(T &a) { cin >> a; } template inline void read(pair &p) { read(p.first), read(p.second); } template inline void read(vector &v) { for(auto &a : v) read(a); } template inline void read(Head &head, Tail &...tail) { read(head), read(tail...); } template inline void chmax(T &a, T b) { (a < b ? a = b : a); } template inline void chmin(T &a, T b) { (a > b ? a = b : a); } // LazySegmentTree template class LazySegTree { private: using F = function; using G = function; using H = function; size_t n; const F f; const G g; const H h; const Monoid e; const Operator oe; vector node; vector lazy; public: LazySegTree(int sz, const F _f, const G _g, const H _h, const Monoid &_e, const Operator &_oe) : f(_f), g(_g), h(_h), e(_e), oe(_oe) { n = 1; while(n < sz) { n <<= 1; } node.resize(2 * n, e); lazy.resize(2 * n, oe); } void set(int k, const Monoid &x) { node[k + n] = x; } void build() { for(int i = n - 1; i > 0; i--) node[i] = f(node[2 * i], node[2 * i + 1]); } // [L,R)区間作用 void update(int L, int R, Operator x) { L += n, R += n; int L0 = L / (L & -L), R0 = R / (R & -R) - 1; thrust(L0); thrust(R0); while(L < R) { if(L & 1) { lazy[L] = h(x, lazy[L]); L++; } if(R & 1) { R--; lazy[R] = h(lazy[R], x); } L >>= 1; R >>= 1; } recalc(L0); recalc(R0); } // [L,R)区間取得 Monoid query(int L, int R) { L += n, R += n; thrust(L / (L & -L)); thrust(R / (R & -R) - 1); Monoid vl = e, vr = e; while(L < R) { if(L & 1) { vl = f(vl, eval(L)); L++; } if(R & 1) { R--; vr = f(eval(R), vr); } L >>= 1; R >>= 1; } return f(vl, vr); } Monoid at(int k) { return query(k, k + 1); } // ノードの評価 inline Monoid eval(int k) { return lazy[k] == oe ? node[k] : g(node[k], lazy[k]); } // 子に伝播 inline void propagate(int k) { if(lazy[k] != oe) { lazy[2 * k] = h(lazy[2 * k], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); node[k] = eval(k); lazy[k] = oe; } } // 上から伝播 inline void thrust(int k) { for(int i = 31 - __builtin_clz(k); i > 0; i--) { if((k >> i) >= 1) propagate(k >> i); } } // 下から再計算 inline void recalc(int k) { while(k > 1) { k >>= 1; node[k] = f(eval(2 * k), eval(2 * k + 1)); } } }; // Range Add and Sum Query // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4955059#1 template struct RASQ : LazySegTree { using Segtree = LazySegTree; static Monoid f(Monoid x1, Monoid x2) { return {x1.first + x2.first, x1.second + x2.second}; } static Monoid g(Monoid x, Operator a) { return {x.first + a * x.second, x.second}; } static auto h(Operator a, Operator b) { return a + b; } RASQ(int n, const Monoid &e = {0, 1}, const Operator &oe = 0) : Segtree(n, f, g, h, e, oe) {} }; class HLDecomposition { Graph g; // グラフ(木) vector sz; // もとの木の部分木のサイズ vector par; // もとの木での親 vector hld; // 訪問済み頂点 vector pre; // 行きがけ順 vector head; // 連結成分のうち最も浅い頂点 vector depth; // もとの木での深さ public: HLDecomposition(Graph &g, int root = 0) : g(g), sz(g.size()), par(g.size()), pre(g.size()), head(g.size()), depth(g.size()) { dfs_sz(root, 0, -1); dfs_hld(root, -1, 0); } int dfs_sz(int v, int d, int p) { par[v] = p; if(sz[v] != 0) return sz[v]; sz[v] = 1; depth[v] = d; for(auto nv : g[v]) { if(p == nv) continue; sz[v] += dfs_sz(nv, d + 1, v); } return sz[v]; } void dfs_hld(int v, int p, int h) { pre[v] = hld.size(); hld.push_back(v); head[v] = h; if(par[v] != -1 && g[v].size() == 1) return; int m = 0; int nxt = -1; for(auto nv : g[v]) { if(nv == p) continue; if(sz[nv] > m) { m = sz[nv]; nxt = nv; } } dfs_hld(nxt, v, h); for(auto nv : g[v]) { if(p == nv) continue; if(nv != nxt) dfs_hld(nv, v, nv); } } vector query(int u, int v) { vector> ret; while(head[u] != head[v]) { if(depth[head[u]] <= depth[head[v]]) { ret.push_back({pre[head[v]], pre[v]}); v = par[head[v]]; } else { ret.push_back({pre[head[u]], pre[u]}); u = par[head[u]]; } } ret.push_back({min(pre[u], pre[v]), max(pre[u], pre[v])}); return ret; } int lca(int u, int v) { for(;; v = par[head[v]]) { if(pre[u] > pre[v]) swap(u, v); if(head[u] == head[v]) return u; } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); INT(n); Graph g(n); rep(i, n - 1) { INT(u, v); u--, v--; g[u].push_back(v); g[v].push_back(u); } HLDecomposition tree(g); RASQ segtree(n); rep(i, n) segtree.set(i, {1, 1}); segtree.build(); INT(q); ll res = 0; rep(i, q) { INT(a, b); a--, b--; auto vec = tree.query(a, b); ll ans = 0; for(auto [l, r] : vec) { ans += segtree.query(l, r + 1).first; } for(auto [l, r] : vec) { segtree.update(l, r + 1, 1); } res += ans; } cout << res << endl; }