#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 HLDecomposition { private: void dfs_size(int u) { size[u] = 1; if (G[u][0] == par[u]) swap(G[u][0], G[u].back()); for (auto &v : G[u]) { if (v == par[u]) continue; par[v] = u; dfs_size(v); size[u] += size[v]; if (size[v] > size[G[u][0]]) swap(v, G[u][0]); } } void dfs_hld(int u, int &k) { in[u] = k++; for (auto v : G[u]) { if (v == par[u]) continue; head[v] = (v == G[u][0] ? head[u] : v); dfs_hld(v, k); } out[u] = k; } // [u -> v) vector> ascend(int u, int v) const { vector> res; while (head[u] != head[v]) { res.emplace_back(in[u], in[head[u]]); u = par[head[u]]; } if (u != v) res.emplace_back(in[u], in[v] + 1); return res; } // (u -> v] vector> descend(int u, int v) const { if (u == v) return {}; if (head[u] == head[v]) return {{in[u] + 1, in[v]}}; auto res = descend(u, par[head[v]]); res.emplace_back(in[head[v]], in[v]); return res; } public: vector> G; int root; vector size, in, out, head, par; HLDecomposition(vector> &_G, int _root = 0) : G(_G), root(_root), size(G.size()), in(G.size(), -1), out(G.size(), -1), head(G.size(), root), par(G.size(), root) { dfs_size(root); int k = 0; dfs_hld(root, k); } void path_query(int u, int v, auto &f, bool vertex = false) { int l = lca(u, v); for (auto&& [a, b] : ascend(u, l)) f(a + 1, b); if (vertex) f(in[l], in[l] + 1); for (auto&& [a, b] : descend(l, v)) f(a, b + 1); } void subtree_query(int u, auto &f, bool vertex = false) { f(in[u] + !f, out[u]); } int lca(int u, int v) { while (head[u] != head[v]) { if (in[u] > in[v]) swap(u, v); v = par[head[v]]; } return in[u] < in[v] ? u : v; } int idx(int u) { return in[u]; } }; // lazy_segtreeで // 区間加算区間和 struct S { ll val; int siz; }; using F = ll; S op(S a, S b) { return {a.val + b.val, a.siz + b.siz}; } S e() { return {0, 0}; } S mapping(F f, S x) { return {x.val + f * x.siz, x.siz}; } F composition(F f, F g) { return f + g; } F id() { return 0; } 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); } HLDecomposition hld(G); lazy_segtree seg(vec(N, {0, 1})); int Q; cin >> Q; ll ans = 0; auto apply = [&] (int u, int v) { if (u > v) swap(u, v); seg.apply(u, v, 1); ans += seg.prod(u, v).val; }; while (Q--) { int a, b; cin >> a >> b; a--; b--; hld.path_query(a, b, apply, true); } cout << ans << '\n'; }