//#define ATCODER_EX_DEBUG #include #include #include #include #include namespace atcoder_ex { template class link_cut_tree { static constexpr bool is_pull_type_v = !std::is_same_v; static constexpr bool is_push_type_v = !std::is_same_v; struct no_value_base {}; struct sum_base { sum_base() : value(e()), sum(e()) {} S value, sum; }; struct sum_apply_base { sum_apply_base() : value(e()), sum(e()), apply(id()) {} S value, sum; F apply; }; struct non_evertable_base {}; struct evertable_base { evertable_base() : rev(false) {} bool rev; }; using v_base = std::conditional_t>; using e_base = std::conditional_t; struct splay_tree_node : public v_base, public e_base { splay_tree_node() : v_base(), e_base(), left(-1), right(-1), parent(-1) {} int left, right, parent; }; using node = splay_tree_node; public: link_cut_tree() : link_cut_tree(0) {} explicit link_cut_tree(int n) : m_size(n), m_nodes(n) {} void link(int v, int p) { expose(v); splay(v); expose(p); splay(v); m_nodes[p].right = v; m_nodes[v].parent = p; pull(p); } void cut(int v) { expose(v); splay(v); int p = m_nodes[v].left; m_nodes[v].left = -1; m_nodes[p].parent = -1; pull(v); } template* = nullptr> void evert(int v) { expose(v); splay(v); std::swap(m_nodes[v].left, m_nodes[v].right); m_nodes[v].rev = true; } int lowest_common_ancester(int u, int v) { expose(u); return expose(v); } template* = nullptr> S get(int v) { push_down_from_top(v); splay(v); return m_nodes[v].value; } template* = nullptr> void set(int v, S x) { push_down_from_top(v); splay(v); m_nodes[v].value = x; pull(v); } template* = nullptr> S prod(int u, int v) { expose(u); int w = expose(v); splay(u); splay(w); S sum = m_nodes[w].value; if (u != w) { sum = op(m_nodes[u].sum, sum); } if (int r = m_nodes[w].right; r != -1) { sum = op(sum, m_nodes[r].sum); } return sum; } template* = nullptr> void apply(int v, F f) { push_down_from_top(v); m_nodes[v].value = mapping(f, m_nodes[v].value); pull_to_top(v); } template* = nullptr> void apply(int u, int v, F f) { expose(u); int w = expose(v); splay(u); splay(w); m_nodes[w].value = mapping(f, m_nodes[w].value); if (u != w) { apply_to_node(u, f); } if (int r = m_nodes[w].right; r != -1) { apply_to_node(r, f); } } void debug() { std::vector visited(m_size); auto dfs = [&](auto self, int v, int p) -> void { visited[v] = true; S sum = m_nodes[v].value; if (int l = m_nodes[v].left; l != -1) { self(self, l, v); sum = op(m_nodes[l].sum, sum); } if (int r = m_nodes[v].right; r != -1) { self(self, r, v); sum = op(sum, m_nodes[r].sum); } bool ok = m_nodes[v].sum == sum; if (!ok) { std::cout << v << std::endl; } }; for (int v = 0; v < m_size; ++v) { if (visited[v]) continue; if (!is_splay_tree_root(v)) continue; dfs(dfs, v, -1); } } private: int expose(int v) { int pre = -1; for (int current = v; current != -1; current = m_nodes[current].parent) { push_down_from_top(current); splay(current); m_nodes[current].right = pre; pull(current); pre = current; } return pre; } void splay(int v) { while (!is_splay_tree_root(v)) { int p = m_nodes[v].parent; int gp = m_nodes[p].parent; if (!is_splay_tree_root(p)) { int ggp = m_nodes[gp].parent; if (ggp != -1) { if (gp == m_nodes[ggp].left) m_nodes[ggp].left = v; else if (gp == m_nodes[ggp].right) m_nodes[ggp].right = v; } m_nodes[v].parent = ggp; if (v == m_nodes[p].left && p == m_nodes[gp].right) { int b = m_nodes[v].right, c = m_nodes[v].left; m_nodes[v].right = p; m_nodes[p].parent = v; m_nodes[v].left = gp; m_nodes[gp].parent = v; m_nodes[p].left = b; if (b != -1) m_nodes[b].parent = p; m_nodes[gp].right = c; if (c != -1) m_nodes[c].parent = gp; } else if (v == m_nodes[p].right && p == m_nodes[gp].left) { int b = m_nodes[v].left, c = m_nodes[v].right; m_nodes[v].left = p; m_nodes[p].parent = v; m_nodes[v].right = gp; m_nodes[gp].parent = v; m_nodes[p].right = b; if (b != -1) m_nodes[b].parent = p; m_nodes[gp].left = c; if (c != -1) m_nodes[c].parent = gp; } else if (v == m_nodes[p].left && p == m_nodes[gp].left) { int b = m_nodes[v].right, c = m_nodes[p].right; m_nodes[v].right = p; m_nodes[p].parent = v; m_nodes[p].right = gp; m_nodes[gp].parent = p; m_nodes[p].left = b; if (b != -1) m_nodes[b].parent = p; m_nodes[gp].left = c; if (c != -1) m_nodes[c].parent = gp; } else { int b = m_nodes[v].left, c = m_nodes[p].left; m_nodes[v].left = p; m_nodes[p].parent = v; m_nodes[p].left = gp; m_nodes[gp].parent = p; m_nodes[p].right = b; if (b != -1) m_nodes[b].parent = p; m_nodes[gp].right = c; if (c != -1) m_nodes[c].parent = gp; } pull(gp); pull(p); pull(v); } else { if (v == m_nodes[p].left) { int x = m_nodes[v].right; m_nodes[p].left = x; if (x != -1) m_nodes[x].parent = p; m_nodes[v].parent = m_nodes[p].parent; m_nodes[v].right = p; m_nodes[p].parent = v; } else { int x = m_nodes[v].left; m_nodes[p].right = x; if (x != -1) m_nodes[x].parent = p; m_nodes[v].parent = m_nodes[p].parent; m_nodes[v].left = p; m_nodes[p].parent = v; } pull(p); pull(v); } } } inline int is_splay_tree_root(int v) const { int p = m_nodes[v].parent; return p == -1 || (m_nodes[p].left != v && m_nodes[p].right != v); } template* = nullptr> inline void pull(int v) { S sum = m_nodes[v].value; if (int l = m_nodes[v].left; l != -1) sum = op(m_nodes[l].sum, sum); if (int r = m_nodes[v].right; r != -1) sum = op(sum, m_nodes[r].sum); m_nodes[v].sum = sum; } template* = nullptr> inline void pull(int) {} template* = nullptr> inline void update_push(int v) { pull(v); } template* = nullptr> inline void update_push(int) {} template* = nullptr> inline void push(int v) { if (m_nodes[v].apply == id()) return; if (int l = m_nodes[v].left; l != -1) { apply_to_node(l, m_nodes[v].apply); } if (int r = m_nodes[v].right; r != -1) { apply_to_node(r, m_nodes[v].apply); } m_nodes[v].apply = id(); if constexpr (Is_Evertable) { eval_rev(v); } } template* = nullptr> inline void push(int v) { if constexpr (Is_Evertable) { eval_rev(v); } } template* = nullptr> inline void apply_to_node(int v, F f) { m_nodes[v].value = mapping(f, m_nodes[v].value); m_nodes[v].sum = mapping(f, m_nodes[v].sum); m_nodes[v].apply = composition(f, m_nodes[v].apply); } template* = nullptr> inline void eval_rev(int v) { if (m_nodes[v].rev) { if (int l = m_nodes[v].left; l != -1) { std::swap(m_nodes[l].left, m_nodes[l].right); m_nodes[l].rev = true; } if (int r = m_nodes[v].right; r != -1) { std::swap(m_nodes[r].left, m_nodes[r].right); m_nodes[r].rev = true; } m_nodes[v].rev = false; } } template* = nullptr> inline void eval_rev(int v) {} void pull_to_top(int v) { while (v != -1) { pull(v); v = m_nodes[v].parent; } } void update_push_to_top(int v) { while (v != -1) { update_push(v); v = m_nodes[v].parent; } } void push_down_from_top(int v) { if (m_nodes[v].parent != -1) { push_down_from_top(m_nodes[v].parent); } push(v); } private: int m_size; std::vector m_nodes; }; } // namespace atcoder_ex #include using namespace std; using ll = long long; using P = std::pair; constexpr P op(P l, P r) { return P(l.first + r.first, l.second + r.second); } constexpr P e() { return P(0, 1); } constexpr P mapping(int l, P r) { return P(r.first + (ll)l * r.second, r.second); } constexpr int composition(int l, int r) { return l + r; } constexpr int id() { return 0; } int main() { std::cin.tie(0); std::ios::sync_with_stdio(0); int N; cin >> N; vector> tree(N); for (int i = 0; i < N - 1; ++i) { int u, v; cin >> u >> v; u--; v--; tree[u].push_back(v); tree[v].push_back(u); } atcoder_ex::link_cut_tree lct(N); auto dfs = [&](auto self, int v, int p) -> void { for (int u : tree[v]) { if (u == p) continue; lct.link(u, v); self(self, u, v); } }; dfs(dfs, 0, -1); int Q; cin >> Q; ll ans = 0; for (int i = 0; i < Q; ++i) { int a, b; cin >> a >> b; a--; b--; lct.apply(a, b, 1); ans += lct.prod(a, b).first; } cout << ans << endl; }