#include #include using namespace std; using namespace atcoder; // type typedef long long ll; typedef long double ld; template using pq = priority_queue; template using pqg = priority_queue, greater>; template using v = vector; #define V vector #define pl pair #define vl v #define vp v #define vm v // IN-OUT #define NYAN ios::sync_with_stdio(false);cin.tie(nullptr);cout< void CIN(T &t, U &...u) { cin >> t; CIN(u...); } void COUT() { cout << "\n"; } template void COUT(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; COUT(u...); } #define dump(x) cerr << #x << ":"<< x << "\n"; #define vdump(x) rep(repeat, sz(x)) cerr << repeat << ":" << x[repeat] << "\n"; // macro #define bp __builtin_popcountll #define ALL(x) x.begin(),x.end() #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define reps(i, s, n) for (ll i = s; i < (ll)(n); i++) #define sz(x) (ll)x.size() ll xd[]={0, 1, 0, -1, 1, 1, -1, -1}; ll yd[]={1, 0, -1, 0, 1, -1, -1, 1}; // function templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b struct hld { int n, root; vector> to; vector par, subsz, in, head; hld(int n) : n(n), to(n), par(n), subsz(n), in(n), head(n) {} void add_edge(int a, int b) { to[a].push_back(b); to[b].push_back(a); } void dfs1(int v, int p) { par[v] = p; subsz[v] = 1; if(to[v].size() && to[v][0] == p) swap(to[v][0], to[v].back()); for(int i = 0; i < (int)to[v].size(); i++) { auto u = to[v][i]; if(u == p) continue; dfs1(u, v); subsz[v] += subsz[u]; if(subsz[to[v][0]] < subsz[u]) swap(to[v][0], to[v][i]); } } void dfs2(int v, int p, int &t) { in[v] = t++; for(auto u : to[v]) { if(u == p) continue; head[u] = (to[v][0] == u ? head[v] : u); dfs2(u, v, t); } } void init(int _root = 0) { root = _root; dfs1(root, -1); int t = 0; dfs2(root, -1, t); } vector> get_edge(int u, int v) { vector> res; while(1) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; res.emplace_back(in[head[v]], in[v] + 1); v = par[head[v]]; } if(in[u] + 1 != in[v] + 1) res.emplace_back(in[u] + 1, in[v] + 1); return res; } vector> get_vertex(int u, int v) { vector> res; while(1) { if(in[u] > in[v]) swap(u, v); if(head[u] == head[v]) break; res.emplace_back(in[head[v]], in[v] + 1); v = par[head[v]]; } res.emplace_back(in[u], in[v] + 1); return res; } }; // hld ------------------------------ using S = pair; S op(S a, S b){return S{a.first + b.first, a.second + b.second};} //セグ木の関数 S e(){return S{0, 0};} //単位元 using F = int; S mapping(F a, S b){return S{b.first, b.second + a * b.first};} //モノイドに作用させるやつ F composition(F a, F b){return {a + b};} //関数合成 bが元の関数 aが新しく合成する関数(注意) F id(){return 0;} //単位元 void solve() { ll n; cin >> n; hld t(n); rep(i, n - 1){ ll a, b; cin >> a >> b; a--; b--; t.add_edge(a, b); } t.init(); lazy_segtree sg(n); rep(i, n) sg.set(i, S{1, 0}); ll q, ans = 0; cin >> q; while(q--){ ll a, b; cin >> a >> b; a--; b--; auto vec = t.get_vertex(a, b); for(auto [l, r] : vec){ sg.apply(l, r, 1); ans += sg.prod(l, r).second; } } cout << ans << "\n"; } int main() { NYAN solve(); return 0; }