#include #include #include struct HLDecomposition { struct Node { int ord, par, depth; int idx; int path_id = -1; Node() {} }; const int N; std::vector> tree, pathes; std::vector nodes; std::vector Q; HLDecomposition(int N) : N(N), tree(N), nodes(N) {} void add_edge(int u, int v) { tree[u].push_back(v); tree[v].push_back(u); } void build(int root = 0) { Q.reserve(N); Q.push_back(root); nodes[root].par = -1; nodes[root].depth = 0; for (int i = 0; i < Q.size(); i++) { int u = Q[i]; auto& U = nodes[u]; U.ord = i; for (int v : tree[u]) { if (U.par == v) continue; auto& V = nodes[v]; V.par = u; V.depth = U.depth + 1; Q.push_back(v); } } decomposition(); } void for_each(int u, int v, std::function f) const { while (nodes[u].path_id != nodes[v].path_id) { int head_u = pathes[nodes[u].path_id][0]; int head_v = pathes[nodes[v].path_id][0]; if (nodes[head_u].depth > nodes[head_v].depth) { std::swap(u, v); std::swap(head_u, head_v); } f(nodes[v].path_id, 0, nodes[v].idx + 1); v = nodes[head_v].par; } if (nodes[v].idx < nodes[u].idx) std::swap(u, v); f(nodes[v].path_id, nodes[u].idx, nodes[v].idx + 1); } int lca(int u, int v) const { int x; for_each(u, v, [&](int p, int l, int r) { x = pathes[p][l]; }); return x; } void decomposition() { std::vector subtree_size(N, 1); for (int i = N - 1; i > 0; i--) { subtree_size[nodes[Q[i]].par] += subtree_size[Q[i]]; } for (int u : Q) { auto& U = nodes[u]; if (U.path_id == -1) { U.path_id = pathes.size(); pathes.emplace_back(); } pathes[U.path_id].push_back(u); int max_subsize = -1, selected = -1; for (int v : tree[u]) { if (U.par == v) continue; if (max_subsize >= subtree_size[v]) continue; max_subsize = subtree_size[v]; selected = v; } if (selected != -1) nodes[selected].path_id = U.path_id; } for (auto&& path : pathes) { for (int i = 0; i < path.size(); i++) { nodes[path[i]].idx = i; } } } }; template struct LazySegTree { using value_type = typename Monoid::value_type; using lazy_type = typename Op::value_type; using Index0 = int; const lazy_type none = Op::none(); const int N, H; std::vector nodes; std::vector lazy; LazySegTree(int size) : LazySegTree(size, 32 - __builtin_clz(size - 1)) {} LazySegTree(int size, int h) : LazySegTree(size, h, 1 << h) {} LazySegTree(int size, int h, int aligned) : N(aligned), H(h), nodes(aligned * 2, Monoid::empty()), lazy(aligned, none) {} inline void apply(int p, lazy_type value, int l, int r) { nodes[p] = Op::eval(nodes[p], value, l, r); if (p < N) lazy[p] = Op::merge(lazy[p], value); } inline void calc(int p, int l, int r) { auto x = Monoid::append(nodes[p << 1], nodes[p << 1 | 1]); if (lazy[p] == none) { nodes[p] = x; } else { nodes[p] = Op::eval(x, lazy[p], l, r); } } void build(Index0 l, Index0 r) { int k = 1; int R = r; for (l += N, r += N - 1; l > 1;) { if (!(r & 1)) R += k; l >>= 1, r >>= 1, k <<= 1; for (int i = r, j = R; i >= l; --i, j -= k) calc(i, j - k, j); } } void push(Index0 l, Index0 r) { int s = H, k = 1 << (H - 1); int L = 0; for (l += N, r += N - 1; s > 0; k >>= 1) { for (int i = l >> s, j = L; i <= r >> s; ++i, j += k) { j += k; if (lazy[i] != none) { apply(i << 1, lazy[i], j - k, j); apply(i << 1 | 1, lazy[i], j, j + k); lazy[i] = none; } } --s; if ((l >> s) & 1) L += k; } } void exec(Index0 l, Index0 r, lazy_type value) { if (value == none) return; int L = l, R = r, k = 1; int i = l, j = r; push(L, L + 1); push(R - 1, R); for (l += N, r += N; l < r; l >>= 1, r >>= 1, k <<= 1) { if (l & 1) { apply(l++, value, i, i + k); i += k; } if (r & 1) { apply(--r, value, j - k, j); j -= k; } } build(L, L + 1); build(R - 1, R); } value_type query(Index0 l, Index0 r) { push(l, l + 1); push(r - 1, r); value_type x = Monoid::empty(); for (l += N, r += N; l < r; l >>= 1, r >>= 1) { if (l & 1) x = Monoid::append(x, nodes[l++]); if (r & 1) x = Monoid::append(x, nodes[--r]); } return x; } }; #include #define mygc(c) (c) = getchar_unlocked() #define mypc(c) putchar_unlocked(c) // clang-format off templateinline T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'inline void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);} // clang-format on using ll = long long; struct Sum { using value_type = ll; static ll empty() { return 0; } static ll append(ll x, ll y) { return x + y; } }; struct Add { using value_type = ll; static ll none() { return 0; } static ll eval(ll x, ll v, int l, int r) { return x + v * (r - l); } static ll merge(ll x, ll y) { return x + y; } }; int main() { int N = rd(); HLDecomposition hl(N); for (int i = 0; i < N - 1; i++) { int u = rd() - 1, v = rd() - 1; hl.add_edge(u, v); } hl.build(); std::vector> segs; segs.reserve(hl.pathes.size()); for (auto&& path : hl.pathes) { segs.emplace_back(path.size() + 1); } int Q = rd(); ll ans = 0; for (int i = 0; i < Q; i++) { int A = rd() - 1, B = rd() - 1; hl.for_each(A, B, [&](int p, int l, int r) { segs[p].exec(l, r, 1); ans += segs[p].query(l, r); }); } wr(ans); return 0; }