#include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; // using mint = modint1000000007; template using vec = vector; template using pa = pair; template using mipq = priority_queue, greater>; #define REP(_1, _2, _3, _4, name, ...) name #define REP1(i, n) for (auto i = decay_t{}; (i) < (n); ++(i)) #define REP2(i, l, r) for (auto i = (l); (i) < (r); ++(i)) #define REP3(i, l, r, d) for (auto i = (l); (i) < (r); i += (d)) #define rep(...) REP(__VA_ARGS__, REP3, REP2, REP1)(__VA_ARGS__) #define rrep(i, r, l) for (int i = (r); i >= (l); --i) template bool chmax(T &a, const T &b) { return (a < b ? a = b, true : false); } template bool chmin(T &a, const T &b) { return (a > b ? a = b, true : false); } constexpr int INF = 1 << 30; constexpr ll LINF = 1LL << 60; constexpr int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; void solve(); int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int T = 1; // cin >> T; while (T--) solve(); } struct LCA { vector> G, parent; vector depth; int N, h; LCA(const vector> &G) : G(G) { N = G.size(); h = 1; while ((1 << h) < N) h++; parent.assign(h, vector(N, -1)); depth.assign(N, -1); dfs(0, -1, 0); for (int k = 0; k < h - 1; k++) { for (int v = 0; v < N; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } void dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int nv : G[v]) { if (nv == p) continue; dfs(nv, v, d + 1); } } int query(int u, int v) { if (depth[u] > depth[v]) swap(u, v); int diff = depth[v] - depth[u]; for (int k = 0; k < h; k++) { if ((diff >> k) & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = h - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[query(u, v)]; } int par(int u) { return parent[0][u]; } }; void solve() { int N; cin >> N; vec> G(N); rep(i, N - 1) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } LCA lca(G); vec s(N); int Q; cin >> Q; while (Q--) { int a, b; cin >> a >> b; a--; b--; int l = lca.query(a, b); s[a]++; s[b]++; s[l]--; l = lca.par(l); if (l != -1) s[l]--; } ll ans = 0; auto dfs = [&] (auto self, int u, int p) -> void { for (auto v : G[u]) { if (v == p) continue; self(self, v, u); s[u] += s[v]; } ans += (ll)s[u] * (s[u] + 1) / 2; }; dfs(dfs, 0, -1); cout << ans << '\n'; }