#include #include struct HLDecomposition { const int N; std::vector> tree; std::vector cluster, par, depth, ord, head, offset; HLDecomposition(int N) : N(N), tree(N), cluster(N, -1), par(N, -1), depth(N), ord(N), offset(N) {} void add_edge(int u, int v) { tree[u].push_back(v); tree[v].push_back(u); } void build(int root = 0) { std::vector Q; Q.reserve(N); Q.push_back(root); for (int i = 0; i < N; i++) { int u = Q[i]; for (int v : tree[u]) { if (par[u] == v) continue; par[v] = u; depth[v] = depth[u] + 1; Q.push_back(v); } } std::vector subtree_size(N, 1); for (int i = N - 1; i > 0; i--) { subtree_size[par[Q[i]]] += subtree_size[Q[i]]; } std::vector> pathes; for (int u : Q) { if (cluster[u] == -1) { cluster[u] = pathes.size(); pathes.emplace_back(); } pathes[cluster[u]].push_back(u); int max_subsize = -1, selected = -1; for (int v : tree[u]) { if (par[u] == v) continue; if (max_subsize >= subtree_size[v]) continue; max_subsize = subtree_size[v]; selected = v; } if (selected != -1) cluster[selected] = cluster[u]; } int P = pathes.size(); head.resize(P + 1); for (int p = 0; p < P; p++) { int H = head[p]; int L = pathes[p].size(); head[p + 1] = H + L; for (int i = 0; i < L; i++) { int v = pathes[p][i]; offset[v] = i; ord[H + i] = v; } } } template void for_each(int u, int v, F f) const { while (cluster[u] != cluster[v]) { if (depth[ord[head[cluster[u]]]] > depth[ord[head[cluster[v]]]]) std::swap(u, v); int h = head[cluster[v]]; f(h, h + offset[v] + 1); v = par[ord[h]]; } if (offset[u] > offset[v]) std::swap(u, v); f(head[cluster[u]] + offset[u], head[cluster[v]] + offset[v] + 1); } int lca(int u, int v) const { int x; for_each(u, v, [&](int l, int r) { x = ord[l]; }); return x; } std::vector> build_pathes() const { const int P = head.size() - 1; std::vector> pathes(P); for (int i = 0; i < P; i++) { pathes[i].reserve(head[i + 1] - head[i]); for (int j = head[i]; j < head[i + 1]; j++) { pathes[i].push_back(ord[j]); } } return pathes; } }; 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(); LazySegTree seg(N); 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 l, int r) { seg.exec(l, r, 1); ans += seg.query(l, r); }); } wr(ans); return 0; }