#include #include #include #include #include #ifdef _MSC_VER #include #endif namespace atcoder { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder namespace atcoder { template struct lazy_segtree { 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())) { log = internal::ceil_pow2(_n); size = 1 << log; 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 using namespace std; using namespace atcoder; #define ll long long struct edge { int from, to; }; int N, Q; vector> G; namespace atcoder { template struct lazy_segtree_hld { public: lazy_segtree_hld() : lazy_segtree_hld(0) {} explicit lazy_segtree_hld(int n, vector> _G) : lazy_segtree_hld(std::vector(n, e()), _G) {} explicit lazy_segtree_hld(const std::vector& v, vector> _G) : _n(int(v.size())) { // ######################################### add ######################################### N = _n; G = _G; parent = vector(N, -1); subtree_size = vector(N); dfs_size(0, -1); depth = vector(N); dfs_depth(0, -1); pre = vector(N); A = vector(N); HLD(0, -1, 0); // ####################################################################################### log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + pre[i]] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } // ######################################### add ######################################### int N; vector> G; vector parent; vector subtree_size; vector depth; vector pre; vector hld_vec; // lowest index in heavy component vector A; void dfs_size(int idx, int par) { parent[idx] = par; subtree_size[idx] = 1; for (auto ee : G[idx]) { if (ee.to == par) continue; dfs_size(ee.to, idx); subtree_size[idx] += subtree_size[ee.to]; } } void dfs_depth(int idx, int par) { depth[idx] = ((par==-1)?0:(depth[par]+1)); for (auto ee : G[idx]) { if (ee.to == par) continue; dfs_depth(ee.to, idx); } } void HLD(int idx, int par, int a) { pre[idx] = hld_vec.size(); hld_vec.push_back(idx); A[idx] = a; int max_size = 0; int max_idx = -1; for (auto ee : G[idx]) { if (ee.to == par) continue; if (subtree_size[ee.to] > max_size) { max_size = subtree_size[ee.to]; max_idx = ee.to; } } if (max_idx == -1) return; HLD(max_idx, idx, a); for (auto ee : G[idx]) { if (ee.to == par) continue; if (ee.to != max_idx) HLD(ee.to, idx, ee.to); } } // ####################################################################################### void set(int p, S x) { // ############ change ############ p = pre[p]; // ################################ 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) { // ############ change ############ p = pre[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); } // ######################################### add ######################################### // path query [l, r] // S prod_path(int l, int r) { // S s_l = e(); // S s_r = e(); // while (A[l] != A[r]) { // if (depth[A[l]] <= depth[A[r]]) { // s_r = op(prod(pre[A[r]], pre[r]+1), s_r); // r = parent[A[r]]; // } else { // s_l = op(prod(pre[A[l]], pre[l]+1), s_l); // l = parent[A[l]]; // } // } // if (pre[l] <= pre[r]) { // s_l.reverse(); // return op(op(s_l, prod(pre[l], pre[r]+1)), s_r); // } else { // assert(pre[r] < pre[l]); // s_r.reverse(); // return op(op(s_r, prod(pre[r], pre[l]+1)), s_l); // } // } S prod_path(int l, int r) { S ret = e(); while (A[l] != A[r]) { if (depth[A[l]] <= depth[A[r]]) { ret = op(ret, prod(pre[A[r]], pre[r]+1)); r = parent[A[r]]; } else { ret = op(ret, prod(pre[A[l]], pre[l]+1)); l = parent[A[l]]; } } ret = op(ret, prod(min(pre[l], pre[r]), max(pre[l], pre[r])+1)); return ret; } S prod_subtree(int p) { return prod(pre[p], pre[p]+subtree_size[p]); } // ####################################################################################### 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); } } // ######################################### add ######################################### // apply path query [l, r] void apply_path(int l, int r, F f) { while (A[l] != A[r]) { if (depth[A[l]] <= depth[A[r]]) { apply(pre[A[r]], pre[r]+1, f); r = parent[A[r]]; } else { apply(pre[A[l]], pre[l]+1, f); l = parent[A[l]]; } } apply(min(pre[l], pre[r]), max(pre[l], pre[r])+1, f); } void apply_subtree(int p, F f) { apply(pre[p], pre[p]+subtree_size[p], f); } // ####################################################################################### 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 struct S { ll sum_val, sz; }; S op(S a, S b) { return S{a.sum_val+b.sum_val, a.sz+b.sz}; } S e() { return S{0, 0}; } using F = long long; S mapping(F f, S a) { return S{a.sum_val+f*a.sz, a.sz}; } F composition(F a, F b) { return a+b; } F id() { return 0LL; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; G = vector>(N, vector()); for (int i=0;i> u >> v; u--;v--; G[u].push_back(edge{u, v}); G[v].push_back(edge{v, u}); } cin >> Q; lazy_segtree_hld seg(N, G); for (int i=0;i> A >> B; A--;B--; seg.apply_path(A, B, 1LL); ans += seg.prod_path(A, B).sum_val; } cout << ans << "\n"; return 0; }