#include #include __attribute__((constructor)) void fast_io() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } class heavy_light_decomposition { public: heavy_light_decomposition(size_t n) : n(n), tree(n), subtree_size(n, 1), parent(n), in(n), out(n), chain_head(n), built(false) {} heavy_light_decomposition(const std::vector>& tree) : heavy_light_decomposition(tree, 0) {} heavy_light_decomposition(const std::vector>& tree, size_t root) : n(tree.size()), tree(tree), subtree_size(n, 1), parent(n), in(n), out(n), chain_head(n), built(false) { assert(root < n); build(root); } void add_edge(size_t u, size_t v) { assert(u < n && v < n); tree[u].push_back(v); tree[v].push_back(u); } void build(size_t root = 0) { dfs_for_size(0, n); size_t time = 0; chain_head[root] = root; dfs_for_hld(root, time); built = true; } size_t operator[](size_t u) const { assert(built && u < n); return in[u]; } size_t lca(size_t u, size_t v) const { assert(built && u < n && v < n); while (true) { if (in[u] > in[v]) std::swap(u, v); if (chain_head[u] == chain_head[v]) return u; v = parent[chain_head[v]]; } } std::pair subtree_query(size_t u) const { assert(built && u < n); return {in[u], out[u]}; } template void subtree_query(size_t u, const F& f) const { assert(built && u < n); f(in[u], out[u]); } // when operation is noncommutative // S resl = e(), resr = e(); // size_t w = hld.lca(u, v) // hld.node_query(u, w, [&](size_t l, size_t r) { resl = op(resl, rseg.prod(l, r)); }); // hld.edge_query(w, v, [&](size_t l, size_t r) { resr = op(seg.prod(l, r), resr); }); // S res = op(resl, resr); std::vector> node_query(size_t u, size_t v) const { assert(built && u < n && v < n); std::vector> result; while (true) { if (in[u] > in[v]) std::swap(u, v); if (chain_head[u] != chain_head[v]) { result.emplace_back(in[chain_head[v]], in[v] + 1); v = parent[chain_head[v]]; } else { result.emplace_back(in[u], in[v] + 1); return result; } } } template void node_query(size_t u, size_t v, const F& f) const { assert(built && u < n && v < n); while (true) { if (in[u] > in[v]) std::swap(u, v); if (chain_head[u] != chain_head[v]) { f(in[chain_head[v]], in[v] + 1); v = parent[chain_head[v]]; } else { f(in[u], in[v] + 1); return; } } } std::vector> edge_query(size_t u, size_t v) const { assert(built && u < n && v < n); std::vector> result; while (true) { if (in[u] > in[v]) std::swap(u, v); if (chain_head[u] != chain_head[v]) { result.emplace_back(in[chain_head[v]], in[v] + 1); v = parent[chain_head[v]]; } else { if (u != v) result.emplace_back(in[u] + 1, in[v] + 1); return result; } } } template void edge_query(size_t u, size_t v, const F& f) const { assert(built && u < n && v < n); while (true) { if (in[u] > in[v]) std::swap(u, v); if (chain_head[u] != chain_head[v]) { f(in[chain_head[v]], in[v] + 1); v = parent[chain_head[v]]; } else { if (u != v) f(in[u] + 1, in[v] + 1); return; } } } private: const size_t n; std::vector> tree; std::vector subtree_size, parent, in, out, chain_head; bool built; void dfs_for_size(size_t u, size_t p) { parent[u] = p; if (!tree[u].empty() && tree[u].front() == p) std::swap(tree[u].front(), tree[u].back()); for (size_t& v : tree[u]) { if (v == p) continue; dfs_for_size(v, u); subtree_size[u] += subtree_size[v]; if (subtree_size[v] > subtree_size[tree[u].front()]) { std::swap(v, tree[u].front()); } } } void dfs_for_hld(size_t u, size_t& time) { in[u] = time++; for (size_t& v : tree[u]) { if (v == parent[u]) continue; chain_head[v] = (v == tree[u].front() ? chain_head[u] : v); dfs_for_hld(v, time); } out[u] = time; } }; using S = std::pair; S op(S a, S b) { return {a.first + b.first, a.second + b.second}; } S e() { return {0, 0}; } using F = long long; S mapping(F f, S x) { return {x.first + f * x.second, x.second}; } F composition(F f, F g) { return f + g; } F id() { return 0; } int main() { size_t n; std::cin >> n; heavy_light_decomposition hld(n); for (size_t i = 0; i < n - 1; ++i) { size_t u, v; std::cin >> u >> v; u--; v--; hld.add_edge(u, v); } hld.build(); atcoder::lazy_segtree seg(std::vector(n, {0, 1})); size_t q; std::cin >> q; long long ans = 0; while (q--) { size_t a, b; std::cin >> a >> b; a--; b--; hld.node_query(a, b, [&](size_t l, size_t r) { seg.apply(l, r, 1); ans += seg.prod(l, r).first; }); } std::cout << ans << '\n'; }