#include #include using namespace std; using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; const int INF = 1e9; //const long long LINF = 1e18; //const bool debug = false; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair template inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } 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; } struct HeavyLightDecomposition { HeavyLightDecomposition(vector> _g, vector&_val) :g(_g), val(_val) { n = g.size(); sz.resize(n); par.resize(n); in.resize(n); out.resize(n); rev.resize(n); head.resize(n); } int n; vector>g; vectorsz, par, in, out, rev, head; vectorval; lazy_segtree seg; void build() { dfs_sz(0); int time = 0; dfs_hld(0, time); initSegmentTree(); } void dfs_sz(int v, int p = -1) { par[v] = p; sz[v] = 1; if (g[v].size() && (p == g[v][0]))swap(g[v][0], g[v].back()); for (auto &e : g[v]) { if (p == e)continue; dfs_sz(e, v); sz[v] += sz[e]; if (sz[g[v][0]] < sz[e])swap(g[v][0], e); } } void dfs_hld(int v, int &time, int p = -1) { in[v] = time; time++; rev[in[v]] = v; for (auto &e : g[v]) { if (p == e)continue; if (e == g[v][0])head[e] = head[v]; else head[e] = e; dfs_hld(e, time, v); } out[v] = time; } void initSegmentTree() { vectora(n); rep(i, n)a[i].value = val[in[i]], a[i].size = 1; lazy_segtree _seg(a); seg = _seg; } int query(int u, int v) { int ret = 0; for (;; v = par[head[v]]) { if (in[u] > in[v])swap(u, v); if (head[u] == head[v])break; ret += seg.prod(in[head[v]], in[v] + 1).value; } ret += seg.prod(in[u], in[v] + 1).value; return ret; } 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; } } void debug() { cout << "in" << endl; rep(i, n) cout << in[i] << " "; cout << endl; cout << "head" << endl; rep(i, n) cout << head[i] << " "; cout << endl; } void update(int u, int v, int x) { for (;; v = par[head[v]]) { if (in[u] > in[v])swap(u, v); if (head[u] == head[v])break; seg.apply(in[head[v]], in[v] + 1, x); } seg.apply(in[u], in[v] + 1, x); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector>g(n); rep(i, n - 1) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } vectorx(n, 0); HeavyLightDecomposition hld(g, x); hld.build(); int q; cin >> q; while (q--) { int a, b; cin >> a >> b; a--; b--; hld.update(a, b, 1); } long long ans = 0; rep(i, n) { long long get = hld.seg.get(i).value; ans += get * (get + 1) / 2; } cout << ans << endl; return 0; }