// Template #include "bits/stdc++.h" #define rep_override(x, y, z, name, ...) name #define rep2(i, n) for (int i = 0; i < (int)(n); ++i) #define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i) #define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__) #define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define all(x) (x).begin(), (x).end() using namespace std; using ll = long long; constexpr int inf = 1001001001; constexpr ll INF = 3003003003003003003LL; template inline bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } return false; } template inline bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } return false; } struct IOSET { IOSET() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } ioset; template istream &operator>>(istream &is, vector &vec) { for (T &element : vec) is >> element; return is; } template ostream &operator<<(ostream &os, vector &vec) { for (int i = 0, vec_len = (int)vec.size(); i < vec_len; ++i) { os << vec[i] << (i + 1 == vec_len ? "" : " "); } return os; } // Heavy-Light Decomposition #include #include template struct HLD { G &g; std::vector sz, par, head, in, rin; HLD(G &_g) : g(_g) { build(); } void build() { sz.assign(g.size(), 0); par.assign(g.size(), 0); dfs_size(0, -1); head.assign(g.size(), 0); in.assign(g.size(), 0); rin.assign(g.size(), 0); int t = 0; dfs_hld(0, -1, t); } int lca(int u, int v) { while (true) { if (in[u] > in[v]) { std::swap(u, v); } if (head[u] == head[v]) { return u; } v = par[head[v]]; } } template T query(int u, int v, const T &identity, const F0 &f0, const F1 &f1, bool edge) { T _u = identity, _v = identity; while (true) { if (in[u] > in[v]) { std::swap(u, v); std::swap(_u, _v); } if (head[u] == head[v]) { break; } _v = f1(f0(in[head[v]], in[v] + 1), _v); v = par[head[v]]; } return f1(f1(f0(in[u] + edge, in[v] + 1), _v), _u); } template void update(int u, int v, const F &f, bool edge) { while (true) { if (in[u] > in[v]) { std::swap(u, v); } if (head[u] == head[v]) { break; } f(in[head[v]], in[v] + 1); v = par[head[v]]; } f(in[u] + edge, in[v] + 1); } private: void dfs_size(int v, int p) { par[v] = p; sz[v] = 1; int l = g[v].size(); if (l && (int)g[v][0] == p) std::swap(g[v][0], g[v][l - 1]); for (int i = 0; i < l; ++i) { if ((int)g[v][i] == p) { continue; } dfs_size((int)g[v][i], v); sz[v] += sz[(int)g[v][i]]; if (sz[(int)g[v][i]] > sz[(int)g[v][0]]) { std::swap(g[v][0], g[v][i]); } } } void dfs_hld(int v, int p, int &t) { in[v] = t++; rin[in[v]] = v; int l = g[v].size(); for (int i = 0; i < l; ++i) { if ((int)g[v][i] == p) { continue; } head[(int)g[v][i]] = (i ? (int)g[v][i] : head[v]); dfs_hld((int)g[v][i], v, t); } } }; // Graph #include #include template class Graph { std::vector> g; public: Graph() : g(0) {} Graph(int n) : g(n) {} Graph(int n, int m) : g(n) { while (m--) { int v; E e; std::cin >> v >> e; add_edge(v, e); } } int size() const { return (int)g.size(); } void add_edge(int from, const E &edge) { g[from].push_back(edge); } const std::vector &operator[](int v) const { return g[v]; } std::vector &operator[](int v) { return g[v]; } }; template struct Wedge { int to; T cost; Wedge(int _to, T _cost) : to(_to), cost(_cost) {} operator int() const { return to; } }; template std::istream &operator>>(std::istream &is, Wedge &e) { is >> e.to >> e.cost; return is; } // Lazy Segment Tree #include #include template class LazySegmentTree { using NodeType = decltype(Operator::node_identity()); using FuncType = decltype(Operator::func_identity()); int length, height, n_; std::vector node; std::vector lazy; std::vector width; void eval(int n) { node[n] = Operator::node_func(node[n], lazy[n], width[n]); if (n < length) { lazy[(n << 1) | 0] = Operator::merge_func(lazy[(n << 1) | 0], lazy[n]); lazy[(n << 1) | 1] = Operator::merge_func(lazy[(n << 1) | 1], lazy[n]); } lazy[n] = Operator::func_identity(); } public: LazySegmentTree(int n) { assert(n >= 0); n_ = n; length = 1; height = 0; while (length < n) { length <<= 1; ++height; } node.resize(length << 1, Operator::node_identity()); lazy.resize(length << 1, Operator::func_identity()); width.resize(length << 1, 1); for (int i = length - 1; i > 0; --i) width[i] = width[i << 1] << 1; } LazySegmentTree(int n, NodeType x) { assert(n >= 0); n_ = n; length = 1; height = 0; while (length < n) { length <<= 1; ++height; } node.resize(length << 1, x); for (int i = length - 1; i > 0; --i) node[i] = Operator::merge_node(node[(i << 1) | 0], node[(i << 1) | 1]); lazy.resize(length << 1, Operator::func_identity()); width.resize(length << 1, 1); for (int i = length - 1; i > 0; --i) width[i] = width[i << 1] << 1; } LazySegmentTree(std::vector &vec) : n_((int)vec.size()) { length = 1; height = 0; while (length < (int)vec.size()) { length <<= 1; ++height; } node.resize(length << 1, Operator::node_identity()); for (int i = 0; i < (int)vec.size(); ++i) node[i + length] = vec[i]; for (int i = length - 1; i > 0; --i) node[i] = Operator::merge_node(node[(i << 1) | 0], node[(i << 1) | 1]); lazy.resize(length << 1, Operator::func_identity()); width.resize(length << 1, 1); for (int i = length - 1; i > 0; --i) width[i] = width[i << 1] << 1; } void update(int a, int b, FuncType x) { assert(a >= 0 && a <= n_ && b >= 0 && b <= n_ && a <= b); int l = a + length, r = b + length - 1; for (int i = height; i > 0; --i) { eval(l >> i); eval(r >> i); } ++r; while (r > l) { if (l & 1) { lazy[l] = Operator::merge_func(lazy[l], x); eval(l); ++l; } if (r & 1) { --r; lazy[r] = Operator::merge_func(lazy[r], x); eval(r); } l >>= 1; r >>= 1; } l = a + length; r = b + length - 1; while (l >>= 1) node[l] = Operator::merge_node(Operator::node_func(node[(l << 1) | 0], lazy[(l << 1) | 0], width[(l << 1) | 0]), Operator::node_func(node[(l << 1) | 1], lazy[(l << 1) | 1], width[(l << 1) | 1])); while (r >>= 1) node[r] = Operator::merge_node(Operator::node_func(node[(r << 1) | 0], lazy[(r << 1) | 0], width[(r << 1) | 0]), Operator::node_func(node[(r << 1) | 1], lazy[(r << 1) | 1], width[(r << 1) | 1])); } void update(int idx, NodeType x) { assert(idx >= 0 && idx < n_); idx += length; for (int i = height; i >= 0; --i) eval(idx >> i); node[idx] = x; while (idx >>= 1) node[idx] = Operator::merge_node(Operator::node_func(node[(idx << 1) | 0], lazy[(idx << 1) | 0], width[(idx << 1) | 0]), Operator::node_func(node[(idx << 1) | 1], lazy[(idx << 1) | 1], width[(idx << 1) | 1])); } NodeType get(int a, int b) { assert(a >= 0 && a <= n_ && b >= 0 && b <= n_ && a <= b); int l = a + length, r = b + length - 1; for (int i = height; i >= 0; --i) { eval(l >> i); eval(r >> i); } ++r; NodeType vl = Operator::node_identity(), vr = Operator::node_identity(); while (l < r) { if (l & 1) { vl = Operator::merge_node(vl, Operator::node_func(node[l], lazy[l], width[l])); ++l; } if (r & 1) { --r; vr = Operator::merge_node(Operator::node_func(node[r], lazy[r], width[r]), vr); } l >>= 1; r >>= 1; } return Operator::merge_node(vl, vr); } }; struct RSQ { using NodeType = long long; using FuncType = long long; static NodeType node_identity() { return 0; } static FuncType func_identity() { return 0; } static NodeType merge_node(NodeType x, NodeType y) { return x + y; } static FuncType merge_func(FuncType x, FuncType y) { return x + y; } static NodeType node_func(NodeType x, FuncType y, int len) { return x + y * len; } }; // Main int main() { int n; cin >> n; Graph g(n); rep(i, n - 1) { int u, v; cin >> u >> v; --u; --v; g.add_edge(u, v); g.add_edge(v, u); } HLD> hld(g); LazySegmentTree seg(n); int q; cin >> q; ll ans = 0; while (q--) { int a, b; cin >> a >> b; --a; --b; hld.update(a, b, [&](int x, int y) {seg.update(x, y, 1);}, false); ans += hld.query(a, b, 0LL, [&](int x, int y) {return seg.get(x, y);}, [&](ll x, ll y) {return x + y;}, false); } cout << ans << "\n"; }