//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,avx512f") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include "./CompetitiveProgrammingCpp/debug.hpp" #include "./CompetitiveProgrammingCpp/Timer.hpp" #include "./CompetitiveProgrammingCpp/sample.hpp" #else #define dump(...) templateconstexpr inline auto d_val(T a, T b) { return a; } #endif /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)((e)-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, (n)) #define RREP(i, n) RFOR(i, 0, (n)) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ template inline auto sort(T& t) { std::sort(ALL(t)); } template inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); } template inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); } template inline auto chmax(T& t, const S& s) { if(s > t) { t = s; return true; } return false; } template inline auto chmin(T& t, const S& s) { if(s < t) { t = s; return true; } return false; } inline auto BR() { std::cout << "\n"; } /* type define */ using ll = long long; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VVVVL = std::vector; using VVVVVL = std::vector; using VD = std::vector; template using V = std::vector; template using P = std::pair; using PAIR = P; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::pair; using std::string; using std::stack; using std::queue; using std::deque; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* Remove the source of the bug */ auto pow(signed, signed) { assert(false); } /* define hash */ namespace std { template <> class hash> { public: size_t operator()(const std::pair& x) const { return hash()(1000000000 * x.first + x.second); } }; } /* input */ template std::istream& operator >> (std::istream& is, vector& vec) { for(T& x : vec) is >> x; return is; } /* constant value */ // constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; //============================================================================================= class SegmentTree { private: const ll m_size; const ll m_initialValue; std::vector m_node; std::vector m_lazy; ll calcSize(ll n) { ll size = 1; while(size < n) { size *= 2; } return size; } public: SegmentTree(ll n, ll val) : m_size(calcSize(n)), m_initialValue(val), m_node(m_size * 2 - 1, m_initialValue), m_lazy(m_size * 2 - 1, m_initialValue) { } void add(ll a, ll b, ll x) { add(a, b + 1, x, 0, 0, m_size); } void add(ll a, ll b, ll x, ll k, ll l, ll r) { eval(k); if(r <= a || b <= l) { return; } if(a <= l && r <= b) { m_lazy[k] += x * (r - l); eval(k); return; } add(a, b, x, 2 * k + 1, l, (l + r) / 2); add(a, b, x, 2 * k + 2, (l + r) / 2, r); m_node[k] = m_node[2 * k + 1] + m_node[2 * k + 2]; } void eval(ll k) { if(m_lazy[k] == m_initialValue) { return; } m_node[k] += m_lazy[k]; if(k < m_size - 1) { m_lazy[2 * k + 1] += m_lazy[k] / 2; m_lazy[2 * k + 2] += m_lazy[k] / 2; } m_lazy[k] = m_initialValue; } ll query(ll a, ll b) { return query(a, b + 1, 0, 0, m_size); } ll query(ll a, ll b, ll k, ll l, ll r) { if(r <= a || b <= l) { return m_initialValue; } eval(k); if(a <= l && r <= b) { return m_node[k]; } return query(a, b, 2 * k + 1, l, (l + r) / 2) + query(a, b, 2 * k + 2, (l + r) / 2, r); } }; class HLD { using node_t = ll; using Graph_f = std::unordered_multimap; using Graph = std::unordered_map>; const node_t m_n; const Graph m_tree; const std::vector m_height; const std::vector> m_root_par; const std::vector m_ids; const std::vector m_order; const std::vector m_edge_ids; static auto constructGraph(node_t n, const Graph_f& tree) { std::deque> order; std::vector used(n); std::stack> stk; stk.emplace(0, -1); used[0] = true; while(!stk.empty()) { auto [f, p] = stk.top(); order.emplace_front(f, p); stk.pop(); auto range = tree.equal_range(f); for(auto itr = range.first; itr != range.second; ++itr) { auto t = itr->second; if(!used[t]) { used[t] = true; stk.emplace(t, f); } } } std::vector size(n, 1); Graph hld_tree; for(const auto& [f, p] : order) { auto range = tree.equal_range(f); node_t size_sum = 1; node_t size_max = 0; std::deque to_list; for(auto itr = range.first; itr != range.second; ++itr) { auto t = itr->second; if(t == p) { continue; } if(size[t] > size_max) { size_max = size[t]; to_list.emplace_back(t); } else { to_list.emplace_front(t); } size_sum += size[t]; } if(!to_list.empty()) { hld_tree.emplace(f, to_list); } size[f] = size_sum; } return hld_tree; } static auto constructRootPar(node_t n, const Graph& tree) { std::vector> root_par(n); std::stack> stk; stk.emplace(0, 0, -1); while(!stk.empty()) { auto [f, root, par] = stk.top(); stk.pop(); if(tree.find(f) == tree.end()) { root_par[f] = {root,par}; continue; } auto itr = tree.at(f).rbegin(); stk.emplace(*itr, root, par); root_par[f] = {root,par}; for(++itr; itr != tree.at(f).rend(); ++itr) { stk.emplace(*itr, *itr, f); } } return root_par; } static auto constructHeight(node_t n, const Graph& tree) { std::vector height(n); std::queue q; q.emplace(0); while(!q.empty()) { auto f = q.front(); q.pop(); if(tree.find(f) == tree.end()) { continue; } for(const auto& t : tree.at(f)) { height[t] = height[f] + 1; q.emplace(t); } } return height; } auto constructIds() const { std::vector ids(m_n); node_t val = 0; std::stack stk; stk.emplace(0); while(!stk.empty()) { auto f = stk.top(); stk.pop(); ids[f] = val; ++val; if(m_tree.find(f) == m_tree.end()) { continue; } for(const auto& t : m_tree.at(f)) { stk.emplace(t); } } return ids; } auto constructOrder()const { std::vector order(m_n); for(ll i = 0; i < m_n; ++i) { order[m_ids[i]] = i; } return order; } /* * 辺をnodeとして拡張した場合の辺nodeだけIDを振る * (1) - (2) * (1) - (e) - (2) * [-1, -1, 0] */ auto constructEdgeIds() const { node_t edge_size = (m_n >> 1); std::vector edge_ids(m_n, -1); node_t val = 0; std::stack stk; stk.emplace(0); while(!stk.empty()) { auto f = stk.top(); stk.pop(); if(f > edge_size) { edge_ids[f] = val; ++val; } if(m_tree.find(f) == m_tree.end()) { continue; } for(const auto& t : m_tree.at(f)) { stk.emplace(t); } } return edge_ids; } public: HLD(node_t n, const Graph_f& tree) : m_n(n), m_tree(constructGraph(n, tree)), m_root_par(constructRootPar(n, m_tree)), m_height(constructHeight(n, m_tree)), m_ids(constructIds()), m_order(constructOrder()), m_edge_ids(constructEdgeIds()) { dump(m_order, m_ids); } auto getId(node_t i)const { return m_ids[i]; } auto getOrder(node_t i)const { return m_order[i]; } auto lca(node_t f, node_t t)const { do { auto [fr, fp] = m_root_par[f]; auto [tr, tp] = m_root_par[t]; if(fr == tr) { break; } auto fph = (fp > -1) ? m_height[fp] : -1; auto tph = (tp > -1) ? m_height[tp] : -1; if(fph < tph) { t = tp; } else { f = fp; } } while(true); return (m_height[f] < m_height[t]) ? f : t; } auto range(node_t f, node_t t)const { std::deque> ret; auto add = [&](node_t f, node_t t) { auto l = std::min(m_ids[f], m_ids[t]); auto r = std::max(m_ids[f], m_ids[t]); ret.emplace_back(l, r); }; do { auto [fr, fp] = m_root_par[f]; auto [tr, tp] = m_root_par[t]; if(fr == tr) { add(f, t); break; } auto fph = (fp > -1) ? m_height[fp] : -1; auto tph = (tp > -1) ? m_height[tp] : -1; if(fph < tph) { add(t, tr); t = tp; } else { add(f, fr); f = fp; } } while(true); return ret; } auto rangeEdge(node_t f, node_t t)const { node_t edge_size = (m_n >> 1); std::deque> ret; auto add = [&](node_t f, node_t t) { auto l = std::min(m_ids[f], m_ids[t]); auto r = std::max(m_ids[f], m_ids[t]); if(m_order[l] <= edge_size) { ++l; } if(m_order[r] <= edge_size) { --r; } if(l > r) { return; } auto edge_l = m_edge_ids[m_order[l]]; auto edge_r = m_edge_ids[m_order[r]]; ret.emplace_back(edge_l, edge_r); }; do { auto [fr, fp] = m_root_par[f]; auto [tr, tp] = m_root_par[t]; if(fr == tr) { add(f, t); break; } auto fph = (fp > -1) ? m_height[fp] : -1; auto tph = (tp > -1) ? m_height[tp] : -1; if(fph < tph) { add(t, tr); t = tp; } else { add(f, fr); f = fp; } } while(true); return ret; } }; signed main() { ll n; cin >> n; unordered_multimap tree; REP(_, n - 1) { ll f, t; cin >> f >> t; --f; --t; tree.emplace(f, t); tree.emplace(t, f); } auto segtree = SegmentTree(n, 0); auto hld = HLD(n, tree); ll q; cin >> q; REP(_, q) { ll a, b; cin >> a >> b; --a; --b; for(const auto& [l, r] : hld.range(a, b)) { segtree.add(l, r, 1); } } ll ans = 0; REP(i, n) { auto val = segtree.query(i, i); ans += val * (val + 1) / 2; } cout << ans << endl; }