#include using namespace std; using ll = long long; class heavy_light_decomposition { public: heavy_light_decomposition(int n_) : n(n_), g(n), par(n), head(n), in(n), out(n) {} heavy_light_decomposition(std::vector> const& g_) : n(g_.size()), g(g_), par(n), head(n), in(n), out(n) {} void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); } void build(int rt = 0) { dfs1(rt); head[rt] = rt; dfs2(rt); } int get_id(int v) const { return in[v]; } void path_query(int u, int v, std::function f) { // vertex while(true) { if(in[u] > in[v]) std::swap(u, v); f(std::max(in[head[v]], in[u]), in[v] + 1); if(head[u] == head[v]) return; v = par[head[v]]; } } void edge_path_query(int u, int v, std::function f) { while(true) { if(in[u] > in[v]) std::swap(u, v); if(head[u] != head[v]) { f(std::max(in[head[v]], in[u]), in[v] + 1); v = par[head[v]]; } else { if(u != v) f(in[u] + 1, in[v] + 1); break; } } } void subtree_query(int v, std::function f) { f(in[v], out[v]); } int get_lca(int u, int v) const { while(true) { if(in[u] > in[v]) std::swap(u, v); if(head[u] == head[v]) return u; v = par[head[v]]; } } private: void dfs1(int rt) { std::vector sz(n, 1), iter(n); std::vector> st = {{rt, -1}}; st.reserve(n); while(!st.empty()) { const int v = st.back().first; if(iter[v] < (int)g[v].size()) { if(g[v][iter[v]] != st.back().second) { st.emplace_back(g[v][iter[v]], v); } ++iter[v]; continue; } par[v] = st.back().second; if(par[v] != -1) { const int pidx = std::find(std::begin(g[v]), std::end(g[v]), par[v]) - std::begin(g[v]); std::swap(g[v].back(), g[v][pidx]); g[v].pop_back(); } for(auto& u : g[v]) { sz[v] += sz[u]; if(sz[u] > sz[g[v].front()]) std::swap(u, g[v].front()); } st.pop_back(); } } void dfs2(int rt) { int it = 0; std::vector st = {rt}, iter(n); st.reserve(n); while(!st.empty()) { const int v = st.back(); if(!iter[v]) in[v] = it++; // first visit if(iter[v] < (int)g[v].size()) { int u = g[v][iter[v]]; head[u] = iter[v] ? u : head[v]; st.push_back(u); ++iter[v]; continue; } out[v] = it; st.pop_back(); } } private: const int n; std::vector> g; std::vector par, head, in, out; }; template class fenwick_tree { public: fenwick_tree(int n_) : n(n_), dat(n, 0) {} void add(int i, T value) { for(; i < n; i |= i + 1) { dat[i] += value; } } T sum(int i) const { T res = 0; for(; i >= 0; i = (i & (i + 1)) - 1) { res += dat[i]; } return res; } // [l, r) T sum(int l, int r) const { return sum(r - 1) - sum(l - 1); } private: const int n; std::vector dat; }; template class range_add_range_sum { public: range_add_range_sum(int n_) : n(n_), bit0(n), bit1(n) {} void add(int l, int r, T val) { bit0.add(l, -val * l); bit1.add(l, val); bit0.add(r, val * r); bit1.add(r, -val); } T sum(int p) const { return bit1.sum(p) * (p + 1) + bit0.sum(p); } T sum(int l, int r) const { return sum(r - 1) - sum(l - 1); } private: const int n; fenwick_tree bit0, bit1; }; int main() { int n; cin >> n; heavy_light_decomposition hld(n); for(int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; hld.add_edge(u - 1, v - 1); } hld.build(); int q; cin >> q; range_add_range_sum rars(n); while(q--) { int a, b; cin >> a >> b; hld.path_query(a - 1, b - 1, [&] (int l, int r) { rars.add(l, r, 1); }); } ll ans = 0; for(int i = 0; i < n; ++i) { const ll t = rars.sum(i, i + 1); ans += t * (t + 1) / 2; } cout << ans << endl; }