#include using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template using V = vector; template using VV = V>; using ll = int64_t; using ull = uint64_t; using PLL = pair; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } // #include "lazysegmenttree.cpp" template struct LazySegmentTree { using Merge = function; using Apply = function; using Update = function; using GenLazy = function; using Propagate = function; ssize_t upper; T init_node; L init_lazy; V node; V lazy; V lazyf; Merge merge; Apply apply; Update update; GenLazy gen_lazy; Propagate prop; public: LazySegmentTree( const V &init_v, T init_node, L init_lazy, Merge merge, Apply apply, Update update, GenLazy gen_lazy, Propagate prop = [](L l) { return l; }) : init_node(init_node), init_lazy(init_lazy), merge(merge), apply(apply), update(update), gen_lazy(gen_lazy), prop(prop) { { upper = 1; while (upper < init_v.size()) upper *= 2; } node.resize(2 * upper - 1, init_node); lazy.resize(2 * upper - 1, init_lazy); lazyf.resize(2 * upper - 1, false); for (ll i = 0; i < init_v.size(); i++) node[i + upper - 1] = init_v[i]; for (ll i = upper - 2; 0 <= i; i--) { ll c0, c1; tie(c0, c1) = get_child_idx(i); node[i] = merge(node[c0], node[c1]); } } PLL get_child_idx(ll pos) { return PLL(2 * pos + 1, 2 * pos + 2); } void push(ll pos, ll nl, ll nr) { if (!lazyf[pos]) return; node[pos] = apply(node[pos], lazy[pos]); if (nr - nl > 1) { ll cidx[2]; tie(cidx[0], cidx[1]) = get_child_idx(pos); for (ll i = 0; i <= 1; i++) { lazy[cidx[i]] = update(lazy[cidx[i]], prop(lazy[pos])); lazyf[cidx[i]] = true; } } lazyf[pos] = false; lazy[pos] = init_lazy; } T update_query(ll ql, ll qr, L val, ll pos, ll nl, ll nr) { push(pos, nl, nr); if (qr <= nl || nr <= ql) return init_node; if (ql <= nl && nr <= qr) { lazy[pos] = gen_lazy(nl, nr, val); lazyf[pos] = true; push(pos, nl, nr); return node[pos]; } else { ll mid = (nl + nr) / 2; ll c0, c1; tie(c0, c1) = get_child_idx(pos); auto lv = update_query(ql, qr, val, c0, nl, mid); auto rv = update_query(ql, qr, val, c1, mid, nr); return node[pos] = merge(node[c0], node[c1]); } } T update_query(ll ql, ll qr, L val) { return update_query(ql, qr, val, 0, 0, upper); } T get_query(ll ql, ll qr, ll pos, ll nl, ll nr) { push(pos, nl, nr); if (nr <= ql || qr <= nl) return init_node; if (ql <= nl && nr <= qr) return node[pos]; ll mid = (nl + nr) / 2; ll c0, c1; tie(c0, c1) = get_child_idx(pos); auto lv = get_query(ql, qr, c0, nl, mid); auto rv = get_query(ql, qr, c1, mid, nr); return merge(lv, rv); } T get_query(ll ql, ll qr) { return get_query(ql, qr, 0, 0, upper); } }; struct HLD { V p_node, head_node, hld_id, heavy , tree_size; HLD(const VV &edges) : p_node(edges.size()), head_node(edges.size()), hld_id(edges.size()), heavy(edges.size(), -1), tree_size(edges.size()) { calc_size(0, -1, edges); ll id = 0; calc_id(0, -1, edges, id); } ll calc_size(ll cur, ll pre, const VV &edges) { ll ret = 1; p_node[cur] = pre; for(ll nxt : edges[cur]) if(nxt != pre) { ret += calc_size(nxt, cur, edges); if(heavy[cur] == -1 || tree_size[heavy[cur]] < tree_size[nxt]) { heavy[cur] = nxt; } } return tree_size[cur] = ret; } void calc_id(ll cur, ll pre, const VV &edges, ll &id) { if(cur == -1) return; hld_id[cur] = id++; if(pre == -1) head_node[cur] = cur; else head_node[cur] = (heavy[pre] == cur ? head_node[pre] : cur); if(cur != heavy[cur]) calc_id(heavy[cur], cur, edges, id); for(ll nxt : edges[cur]) { if(nxt == pre || nxt == heavy[cur]) continue; calc_id(nxt, cur, edges, id); } } ll head_id(ll node) { return hld_id[head_node[node]]; } ll lca(ll n1, ll n2) { while(true) { if(hld_id[n2] < hld_id[n1]) swap(n1, n2); if(head_node[n1] == head_node[n2]) break; n2 = p_node[head_node[n2]]; } return n1; } // calc's arg is [l, r) template T query(ll n1, ll n2, function calc, T id_ele, function merge) { T lval = id_ele, rval = id_ele; T res = id_ele; while(true) { ll id1 = hld_id[n1]; ll id2 = hld_id[n2]; if(head_node[n1] != head_node[n2]) { if(id1 < id2) { auto tmp = calc(head_id(n2), id2 + 1); rval = merge(tmp, rval); n2 = p_node[head_node[n2]]; } else { auto tmp = calc(head_id(n1), id1 + 1); lval = merge(lval, tmp); n1 = p_node[head_node[n1]]; } } else { if(id2 < id1) swap(id1, id2); res = calc(id1, id2 + 1); res = merge(lval, merge(res, rval)); break; } } return res; } void query(ll n1, ll n2, function update) { ll identity = 0; auto merge = [&](ll a, ll b) { return 0; }; auto wrapper_calc = [&](ll a, ll b) { update(a, b); return 0; }; query(n1, n2, wrapper_calc, identity, merge); } }; int main() { ll N; cin >> N; VV edges(N); for(ll i = 1; i < N; i++) { ll a, b; cin >> a >> b; a--; b--; edges[a].push_back(b); edges[b].push_back(a); } HLD hld(edges); LazySegmentTree lst(V(N, 1), 0, 0, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; }, [](ssize_t l, ssize_t r, ll v) { return (r - l) * v; }, [](ll v) { return v / 2; }); auto merge = [&](ll a, ll b) { return a + b; }; auto update = [&](ll a, ll b) { lst.update_query(a, b, 1); }; auto calc_tax = [&](ll a, ll b) { return lst.get_query(a, b); }; ll Q; cin >> Q; ll ans = 0; while(Q--) { ll u, v; cin >> u >> v; u--; v--; ans += hld.query(u, v, calc_tax, 0, merge); hld.query(u, v, update); } cout << ans << endl; return 0; }