#include using namespace std; #define INF_LL (int64)1e18 #define INF (int32)1e9 #define REP(i, n) for(int64 i = 0;i < (n);i++) #define FOR(i, a, b) for(int64 i = (a);i < (b);i++) #define all(x) x.begin(),x.end() #define fs first #define sc second using int32 = int_fast32_t; using uint32 = uint_fast32_t; using int64 = int_fast64_t; using uint64 = uint_fast64_t; using PII = pair; using PLL = pair; const double eps = 1e-10; templateinline void chmin(A &a, B b){if(a > b) a = b;} templateinline void chmax(A &a, B b){if(a < b) a = b;} class HLDecomposition{ private: vector> G; vector vid, inv, dep, par, typ, sub, head, in, out; int32 n, pos; public: HLDecomposition(){} HLDecomposition(int32 n): n(n), pos(0), G(n), vid(n, -1), inv(n), dep(n, -1), par(n), typ(n), sub(n, 1), head(n), in(n, -1), out(n, -1){} void add_edge(int32 u, int32 v){ G[u].push_back(v); G[v].push_back(u); } void build(){ int32 type = 0; for(int32 i = 0;i < n;i++){ if(dep[i] == -1){ dfs(i); dfs2(i, type++); } } } void dfs(int32 v){ using T = pair; dep[v] = 0; par[v] = -1; stack st; st.emplace(v, 0); while(st.size()){ v = st.top().first; int32 &i = st.top().second; if(i sub[0]){ swap(u, G[v][0]); } } } } } void dfs2(int32 v, int32 t){ using T = tuple; stack st; st.emplace(v, 0, v); while(st.size()){ v = get<0>(st.top()); int32 &i = get<1>(st.top()); int32 h = get<2>(st.top()); if(i == 0){ typ[v] = t; in[v] = pos; out[v] = in[v]+sub[v]-1; vid[v] = pos++; inv[vid[v]] = v; head[v] = h; } if(i& f){ while(1){ if(vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if(head[u] != head[v]) v=par[head[v]]; else break; } } void for_each_edge(int32 u, int32 v, const function& f){ while(1){ if(vid[u] > vid[v]) swap(u, v); if(head[u] != head[v]){ f(vid[head[v]], vid[v]); v = par[head[v]]; }else{ if(u!=v) f(vid[u]+1, vid[v]); break; } } } void for_subtree(int32 u, const function& f){ if(in[u] == -1){ cout << "Invalid vertex." << endl; return; } f(in[u], out[u]); } int32 lca(int32 u, int32 v){ while(1){ if(vid[u] > vid[v]) swap(u, v); if(head[u] != head[v]) v = par[head[v]]; else return u; } } int32 distance(int32 u, int32 v){ return dep[u]+dep[v]-2*dep[lca(u, v)]; } int32 getvid(int32 v){ return vid[v]; } }; template class LazySegTree{ private: using F = function; using G = function; using H = function; using P = function; int32 n; vector node; vector lazy; F f; G g; H h; P p; T ti; E ei; public: LazySegTree(){} LazySegTree(int32 _n, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){ init(_n); } LazySegTree(vector v, F f, G g, H h, T ti, E ei, P p = [](E a, int32 b){return a;}):f(f), g(g), h(h), p(p), ti(ti), ei(ei){ init(v.size()); for(int32 i = 0;i < v.size();i++) node[i+n-1] = v[i]; for(int32 i = n-2;i >= 0;i--) node[i] = merge(node[i*2+1], node[i*2+2]); } void init(int32 _n){ n = 1; while(n < _n) n*=2; node.resize(2*n-1, ti); lazy.resize(2*n-1, ei); } inline T merge(T lhs, T rhs){ if(lhs == ti) return rhs; else if(rhs == ti) return lhs; return f(lhs, rhs); } inline void eval(int32 k, int32 l, int32 r){ if(lazy[k] == ei) return; node[k] = g(node[k], p(lazy[k], r-l)); if(r-l > 1){ lazy[k*2+1] = h(lazy[k*2+1], lazy[k]); lazy[k*2+2] = h(lazy[k*2+2], lazy[k]); } lazy[k] = ei; } T update(int32 a, int32 b, E x, int32 k=0, int32 l=0, int32 r=-1){ if(r<0) r = n; eval(k, l, r); if(b <= l || r <= a) return node[k]; if(a <= l && r <= b){ lazy[k] = h(lazy[k], x); return g(node[k], p(lazy[k], r-l)); } return node[k] = merge(update(a, b, x, k*2+1, l, (l+r)/2), update(a, b, x, k*2+2, (l+r)/2, r)); } T query(int32 a, int32 b, int32 k=0, int32 l=0, int32 r=-1){ if(r<0) r = n; eval(k, l, r); if(b <= l || r <= a) return ti; if(a <= l && r <= b) return node[k]; return merge(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r)); } }; int main(void){ int32 N, Q; cin >> N; HLDecomposition hld(N); LazySegTree lsg(N, [](int64 a, int64 b){return a+b;}, [](int64 a, int64 b){return a+b;}, [](int64 a, int64 b){return a+b;}, 0, 0); REP(i, N-1){ int32 u, v; cin >> u >> v; u--; v--; hld.add_edge(u, v); } hld.build(); cin >> Q; auto f = [&](int32 u, int32 v){ lsg.update(u, v+1, 1); }; REP(i, Q){ int32 A, B; cin >> A >> B; A--; B--; hld.for_each(A, B, f); } int64 res = 0; REP(i, N){ int64 x = lsg.query(i, i+1); res += x*(x+1)/2; } cout << res << endl; }