// #pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using ull = unsigned long long; using vecint = std::vector; using vecll = std::vector; using vecstr = std::vector; using vecbool = std::vector; using vecdou = std::vector; using vecpl = std::vector>; using vec2d = std::vector; using vec2di = std::vector; using vec2dd = std::vector; using vec2db = std::vector; using pl = pair; #define rep(i,n) for (ll i = 0; i < (ll)(n); i++) #define rep1(i,n) for (ll i = 1; i <= (ll)(n); i++) #define REP(i,l,r) for (ll i = (ll)(l); i < (ll)(r); i++) #define rrep(i,n) for (ll i = (ll)(n)-1; i >= 0; i--) #define rrep1(i,n) for (ll i = (ll)(n); i > 0; i--) #define RREP(i,l,r) for (ll i = (ll)(r)-1; i >= (ll)(l); i--) #define all(a) (a).begin(), (a).end() #define INF ((1LL<<62)-(1LL<<31)) #define inr(a,x,b) ((a) <= (x) && (x) < (b)) template bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } void ynout(bool x,string Tru="Yes",string Wro="No"){ if(x){ cout << Tru << '\n'; }else{ cout << Wro << '\n'; } } ll power(ll a,ll b,ll mod=INF){ long long x=1,y=a%mod; while(b>0){ if(b&1ll){ x=(x*y)%mod; } y=(y*y)%mod; b>>=1; } return x%mod; } ll Pdist2(pair a,pair b){ return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); } double Pdist(pair a,pair b){ return sqrt(Pdist2(a,b)); } ll PdistM(pair a,pair b){ return abs(a.first-b.first)+abs(a.second-b.second); } ll gcd(ll a,ll b){ if(b==0){ return a; }else{ return gcd(b,a%b); } } ll lcm(ll a,ll b){ return a/gcd(a,b)*b; } template void print(const std::vector& v) { for (const auto& elem : v) { cout << elem << " "; } cout << '\n'; } template void print2d(const std::vector>& v) { for (const auto& row : v) { for (const auto& elem : row) { cout << elem << " "; } cout << '\n'; } } vecll vecinp(ll n){ vecll v(n); rep(i,n) cin >> v[i]; return v; } void solve(); int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); ll t=1; // std::cin >> t; rep(i,t)solve(); } // vecll dx = {1,0,-1,0}; // vecll dy = {0,1,0,-1}; // vector dir = {'D','R','U','L'}; // begin include: libraries/HLD_lseg.hpp #include // begin include: atcoder/lazysegtree // begin include: atcoder/lazysegtree.hpp #include #include #include #include // begin include: atcoder/internal_bit // begin include: atcoder/internal_bit.hpp #ifdef _MSC_VER #include #endif #if __cplusplus >= 202002L #include #endif namespace atcoder { namespace internal { #if __cplusplus >= 202002L using std::bit_ceil; #else // @return same with std::bit::bit_ceil unsigned int bit_ceil(unsigned int n) { unsigned int x = 1; while (x < (unsigned int)(n)) x *= 2; return x; } #endif // @param n `1 <= n` // @return same with std::bit::countr_zero int countr_zero(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } // @param n `1 <= n` // @return same with std::bit::countr_zero constexpr int countr_zero_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } } // namespace internal } // namespace atcoder // end include: atcoder/internal_bit.hpp // end include: atcoder/internal_bit namespace atcoder { #if __cplusplus >= 201703L template struct lazy_segtree { static_assert(std::is_convertible_v>, "op must work as S(S, S)"); static_assert(std::is_convertible_v>, "e must work as S()"); static_assert( std::is_convertible_v>, "mapping must work as F(F, S)"); static_assert( std::is_convertible_v>, "compostiion must work as F(F, F)"); static_assert(std::is_convertible_v>, "id must work as F()"); #else template struct lazy_segtree { #endif public: lazy_segtree() : lazy_segtree(0) {} explicit lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} explicit lazy_segtree(const std::vector& v) : _n(int(v.size())) { size = (int)internal::bit_ceil((unsigned int)(_n)); log = internal::countr_zero((unsigned int)size); d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder // end include: atcoder/lazysegtree.hpp // end include: atcoder/lazysegtree using namespace std; using ll = long long; using vecll = std::vector; #define rep(i,n) for (ll i = 0; i < (ll)(n); i++) template struct HLD_lseg { vecll vertex; vecll id; vecll head; vecll parent; vecll depth; vecll subsize; vecll heavy_child; int root; static S op_rev(S a, S b) { return op(b, a); } atcoder::lazy_segtree seg; atcoder::lazy_segtree seg_rev; HLD_lseg(const vector>& graph, int root_ = 0) { root = root_; int n = graph.size(); vertex.resize(n); id.resize(n); head.resize(n); parent.resize(n); depth.resize(n); subsize.resize(n); heavy_child.resize(n); seg = atcoder::lazy_segtree(n); seg_rev = atcoder::lazy_segtree(n); { function dfs = [&](int v, int p, int d) { parent[v] = p; depth[v] = d; subsize[v] = 1; heavy_child[v] = -1; int max_subsize = 0; for (int to : graph[v]) { if (to == p) continue; dfs(to, v, d + 1); subsize[v] += subsize[to]; if (subsize[to] > max_subsize) { max_subsize = subsize[to]; heavy_child[v] = to; } } }; dfs(root, -1, 0); } { int idx = 0; function dfs = [&](int v, int h) { head[v] = h; id[v] = idx; vertex[idx] = v; idx++; if (heavy_child[v] != -1) { dfs(heavy_child[v], h); } for (int to : graph[v]) { if (to == parent[v] || to == heavy_child[v]) continue; dfs(to, to); } }; dfs(root, root); } } HLD_lseg(const vector>& graph, const vector& initial_values, int root_ = 0) { root = root_; int n = graph.size(); vertex.resize(n); id.resize(n); head.resize(n); parent.resize(n); depth.resize(n); subsize.resize(n); heavy_child.resize(n); seg = atcoder::lazy_segtree(n); seg_rev = atcoder::lazy_segtree(n); { function dfs = [&](int v, int p, int d) { parent[v] = p; depth[v] = d; subsize[v] = 1; heavy_child[v] = -1; int max_subsize = 0; for (int to : graph[v]) { if (to == p) continue; dfs(to, v, d + 1); subsize[v] += subsize[to]; if (subsize[to] > max_subsize) { max_subsize = subsize[to]; heavy_child[v] = to; } } }; dfs(root, -1, 0); } { int idx = 0; function dfs = [&](int v, int h) { head[v] = h; id[v] = idx; vertex[idx] = v; idx++; if (heavy_child[v] != -1) { dfs(heavy_child[v], h); } for (int to : graph[v]) { if (to == parent[v] || to == heavy_child[v]) continue; dfs(to, to); } }; dfs(root, root); } rep(i,n) { seg.set(id[i], initial_values[i]); seg_rev.set(id[i], initial_values[i]); } } // vの祖先で深さがdのものを返す int level_ancestor(int v, int d) { if (depth[v] < d) return -1; while (depth[head[v]] > d) { v = parent[head[v]]; } return vertex[id[v] - (depth[v] - d)]; } // uとvのLCAを返す int lca(int u, int v) { while (head[u] != head[v]) { if (depth[head[u]] > depth[head[v]]) { u = parent[head[u]]; } else { v = parent[head[v]]; } } return depth[u] < depth[v] ? u : v; } // uとvの距離を返す int distance(int u, int v) { int l = lca(u, v); return depth[u] + depth[v] - 2 * depth[l]; } // s->tのパス上i番目の頂点を返す int jump(int s, int t, int i) { int l = lca(s, t); if (i <= depth[s] - depth[l]) { return level_ancestor(s, depth[s] - i); } else { return level_ancestor(t, i - depth[s] + 2*depth[l]); } } // vの値をxに更新 void set(int v, S x) { seg.set(id[v], x); seg_rev.set(id[v], x); } S get(int i) { return seg.get(id[i]); } // s->tのパス(v0,...,vk)に対し、v0・...・vkを返す S prod_path(int s, int t) { int l = lca(s, t); S res_left = e(), res_right = e(); while (head[s] != head[l]) { res_left = op(res_left, seg_rev.prod(id[head[s]], id[s] + 1)); s = parent[head[s]]; } res_left = op(res_left, seg_rev.prod(id[l], id[s] + 1)); while (head[t] != head[l]) { res_right = op(seg.prod(id[head[t]], id[t] + 1), res_right); t = parent[head[t]]; } res_right = op(seg.prod(id[l] + 1, id[t] + 1), res_right); return op(res_left, res_right); } void apply_path(int s, int t, F f) { int l = lca(s, t); while (head[s] != head[l]) { seg.apply(id[head[s]], id[s] + 1, f); seg_rev.apply(id[head[s]], id[s] + 1, f); s = parent[head[s]]; } seg.apply(id[l], id[s] + 1, f); seg_rev.apply(id[l], id[s] + 1, f); while (head[t] != head[l]) { seg.apply(id[head[t]], id[t] + 1, f); seg_rev.apply(id[head[t]], id[t] + 1, f); t = parent[head[t]]; } seg.apply(id[l] + 1, id[t] + 1, f); seg_rev.apply(id[l] + 1, id[t] + 1, f); } }; // end include: libraries/HLD_lseg.hpp 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; } void solve(){ ll n; cin>>n; vec2d g(n); rep(i,n-1){ ll u,v; cin>>u>>v; u--;v--; g[u].emplace_back(v); g[v].emplace_back(u); } vector v(n,{1,1}); HLD_lseg hld(g,v); ll q; cin>>q; ll ans = 0; while(q--){ ll a,b; cin>>a>>b; a--;b--; ans += hld.prod_path(a,b).value; hld.apply_path(a,b,1); } cout << ans << '\n'; }