#include #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef tuple t3; typedef tuple t4; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) #include using namespace std; template void chmax(T& reference, T value) { reference = max(reference, value); } template void chmaxmap(map& m, T key, T value) { if (m.count(key)) { chmax(m[key], value); } else { m[key] = value; } } template void chmin(T& reference, T value) { reference = min(reference, value); } #include using namespace atcoder; template< typename G > struct HeavyLightDecomposition { G& g; vector< int > sz, in, out, head, rev, par; HeavyLightDecomposition(G& g) : g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {} void dfs_sz(int idx, int p) { par[idx] = p; sz[idx] = 1; if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back()); for (auto& to : g[idx]) { if (to == p) continue; dfs_sz(to, idx); sz[idx] += sz[to]; if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to); } } void dfs_hld(int idx, int par, int& times) { in[idx] = times++; rev[in[idx]] = idx; for (auto& to : g[idx]) { if (to == par) continue; head[to] = (g[idx][0] == to ? head[idx] : to); dfs_hld(to, idx, times); } out[idx] = times; } void build() { dfs_sz(0, -1); int t = 0; dfs_hld(0, -1, t); } int la(int v, int k) { while (1) { int u = head[v]; if (in[v] - k >= in[u]) return rev[in[v] - k]; k -= in[v] - in[u] + 1; v = par[u]; } } int lca(int u, int v) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) return u; } } template< typename T, typename Q, typename F > T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) { T l = ti, r = ti; for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v), swap(l, r); if (head[u] == head[v]) break; l = f(q(in[head[v]], in[v] + 1), l); } return f(f(q(in[u] + edge, in[v] + 1), l), r); } template< typename Q > void add(int u, int v, const Q& q, bool edge = false) { for (;; v = par[head[v]]) { if (in[u] > in[v]) swap(u, v); if (head[u] == head[v]) break; q(in[head[v]], in[v] + 1); } q(in[u] + edge, in[v] + 1); } }; typedef vector> UnWeightedGraph; struct S { long long value; int size; }; using F = long long; S op(S a, S b) { return { a.value + b.value, a.size + b.size }; } S e() { return { 0, 0 }; } S mapping(F f, S x) { return { x.value + f * x.size, x.size }; } F composition(F f, F g) { return f + g; } F id() { return 0; } int main() { int n; cin >> n; vector> g(n); rep(i, n - 1) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } HeavyLightDecomposition hld(g); hld.build(); lazy_segtree tree(n); rep(i, n) tree.set(i, { 0LL, 1 }); int q; cin >> q; ll ans = 0; rep(i, q) { int a, b; cin >> a >> b; a--; b--; ll cost = hld.query(a, b, 0LL, [&](int x, int y) { auto p = tree.prod(x, y); return p.value + p.size; }, [&](ll x, ll y) { return x + y; }); //cout << cost << endl; ans += cost; hld.add(a, b, [&](int x, int y) { tree.apply(x, y, 1LL); }); } cout << ans << endl; return 0; }