#include #include #include #include #include #include #include using namespace atcoder; using namespace std; using ll = long long; class heavy_light_decomposition { private: int N_, count_edge_ = 0; std::map, int> edge_idx_; std::vector> edge_by_order_; std::vector sub_, depth_, parent_, head_, order_, order_inverse_; struct edge {int idx; int to;}; std::vector> edge_; bool build_flag_ = false; atcoder::dsu union_find; int calculate_tree_information(int v = 0, int p = -1){ sub_[v] = 1; depth_[v] = p == -1 ? 0 : depth_[p] + 1; parent_[v] = p; if(!edge_[v].empty() && edge_[v][0].to == p) std::swap(edge_[v][0], edge_[v].back()); for(edge &e : edge_[v]){ if(e.to == p) continue; sub_[v] += calculate_tree_information(e.to, v); if(sub_[e.to] > sub_[edge_[v][0].to]) std::swap(e, edge_[v][0]); } return sub_[v]; } void construct_heavy_leght_decomposition(int &i, int v = 0){ order_[v] = i; order_inverse_[i++] = v; for(edge e : edge_[v]){ if(e.to == parent_[v]) continue; head_[e.to] = (e.to == edge_[v][0].to ? head_[v] : e.to); construct_heavy_leght_decomposition(i, e.to); } return; } void build_(){ assert(N_ == count_edge_ + 1); calculate_tree_information(); int i = 0; construct_heavy_leght_decomposition(i); build_flag_ = true; return; } public: heavy_light_decomposition(int N){ N_ = N; edge_by_order_.resize(N); sub_.resize(N); depth_.resize(N); parent_.resize(N); head_.resize(N); order_.resize(N); order_inverse_.resize(N); edge_.resize(N); union_find = atcoder::dsu(N); } int add_edge(int v, int u){ assert(!union_find.same(v, u)); union_find.merge(v, u); edge_[v].push_back({count_edge_, u}); edge_[u].push_back({count_edge_, v}); edge_idx_[{v, u}] = edge_idx_[{u, v}] = count_edge_; edge_by_order_[count_edge_] = {v, u}; return count_edge_++; } std::pair get_edge(int idx){ assert(idx < count_edge_); return edge_by_order_[idx]; } int get_edge_idx(int v, int u){ return edge_idx_.count({v, u}) ? edge_idx_[{v, u}] : -1; } int lca(int v, int u){ if(!build_flag_) build_(); while(head_[v] != head_[u]){ if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u); u = parent_[head_[u]]; } int i = std::min(order_[v], order_[u]); return order_inverse_[i]; } int get_hldidx_vertex(int v){ if(!build_flag_) build_(); return order_[v]; } std::vector> subtree_query(int v){ if(!build_flag_) build_(); return std::vector>{{order_[v], order_[v] + sub_[v]}}; } std::vector> path_query_vertex(int v, int u){ if(!build_flag_) build_(); std::vector> res; while(head_[v] != head_[u]){ if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u); res.emplace_back(order_[head_[u]], order_[u] + 1); u = parent_[head_[u]]; } if(order_[v] > order_[u]) std::swap(v, u); res.emplace_back(order_[v], order_[u] + 1); return res; } int get_hldidx_edge(int idx){ if(!build_flag_) build_(); auto [v, u] = edge_by_order_[idx]; if(v == parent_[u]) std::swap(v, u); return order_[v] - 1; } int get_hldidx_edge(int v, int u){ if(!build_flag_) build_(); assert(edge_idx_.count({v, u})); if(v == parent_[u]) std::swap(v, u); return order_[v] - 1; } std::vector> path_query_edge(int v, int u){ if(!build_flag_) build_(); std::vector> res; while(head_[v] != head_[u]){ if(depth_[head_[v]] > depth_[head_[u]]) std::swap(v, u); res.emplace_back(order_[head_[u]] - 1, order_[u]); u = parent_[head_[u]]; } if(order_[v] > order_[u]) std::swap(v, u); res.emplace_back(order_[v], order_[u]); return res; } }; struct S{ int length; ll sum; }; S op(S a, S b){ return {a.length + b.length, a.sum + b.sum}; } S e(){ return {0, 0LL}; } using F = int; S mapping(F f, S x){ return {x.length, ll(f) * x.length + x.sum}; } F composition(F f, F g){ return f + g; } F id(){ return 0LL; } int main(){ int N; cin >> N; heavy_light_decomposition graph(N); for(int i = 0; i < N - 1; i++){ int u, v; cin >> u >> v; u--; v--; graph.add_edge(u, v); } int Q; cin >> Q; lazy_segtree seg(vector(N, {1, 0})); ll ans = 0; for(int _ = 0; _ < Q; _++){ int A, B; cin >> A >> B; A--; B--; for(auto [l, r] : graph.path_query_vertex(A, B)){ seg.apply(l, r, 1); ans += seg.prod(l, r).sum; } } cout << ans << '\n'; return 0; }