#include using namespace std; // 区間加算,区間参照 // 半開区間!!! template class RangeAddQuery { private: vector data, lazy; int sz; void push(int k, int l, int r) { if (this->lazy[k]) { this->data[k] += this->lazy[k] * (r - l); if (k * 2 + 2 < sz * 2 - 1) { this->lazy[2 * k + 1] += this->lazy[k]; this->lazy[2 * k + 2] += this->lazy[k]; } this->lazy[k] = 0; } } void add(int l, int r, int L, int R, int k, T val) { this->push(k, l, r); if (L <= l && r <= R) { this->lazy[k] += val; this->push(k, l, r); } else if (R <= l || r <= L) { return; } else if (r - l > 1) { const int mid = (l + r) / 2; this->add(l, mid, L, R, k * 2 + 1, val); this->add(mid, r, L, R, k * 2 + 2, val); data[k] = data[k * 2 + 1] + data[k * 2 + 2]; } } T query(int l, int r, int L, int R, int k) { this->push(k, l, r); if (L <= l && r <= R) { return data[k]; } else if (R <= l || r <= L) { return 0; } else { const int mid = (l + r) / 2; const T left = this->query(l, mid, L, R, k * 2 + 1); const T right = this->query(mid, r, L, R, k * 2 + 2); return left + right; } } public: RangeAddQuery(const int n) { this->sz = 1; while (this->sz < n) this->sz <<= 1; this->data.resize(this->sz * 2 - 1); this->lazy.resize(this->sz * 2 - 1); } void add(int l, int r, T val) { this->add(0, this->sz, l, r, 0, val); } T query(int l, int r) { return this->query(0, this->sz, l, r, 0); } }; class HeavyLightDecomposition { private: int N, pos; std::vector> G; std::vector parent; std::vector depth; std::vector heavy; // next node of heavy path std::vector sub_tree_cnt; std::vector maximum_sub_tree_cnt; std::vector tree_th_num; // what number of tree ? std::vector vid, inv_vid; // re numbering node for decomp (vertex_index) std::vector head; // root of SubTree in this node public: HeavyLightDecomposition() {} HeavyLightDecomposition(int g_size) : N(g_size), G(g_size), parent(g_size), depth(g_size), heavy(g_size, -1), sub_tree_cnt(g_size), pos(0), tree_th_num(g_size), head(g_size), vid(g_size), inv_vid(g_size) {} void add_edge(const int a, const int b) { this->G[a].emplace_back(b); this->G[b].emplace_back(a); } // if forest, tree roots in argument void build(const std::vector roots = std::vector(1, 0)) { for (int th = 0; th < roots.size(); th++) { this->dfs(roots[th], -1); this->bfs(roots[th], th); } } // calc SubTree count of this node int dfs(const int now, const int prev) { parent[now] = prev; int sub_tree_all_cnt = 1; // include now node int max_sub_tree_cnt = 0; for (auto &&nxt : this->G[now]) { if (nxt == prev) { continue; } this->depth[nxt] = this->depth[now] + 1; const int now_sub_tree_cnt = this->dfs(nxt, now); sub_tree_all_cnt += now_sub_tree_cnt; if (max_sub_tree_cnt < now_sub_tree_cnt) { max_sub_tree_cnt = now_sub_tree_cnt; this->heavy[now] = nxt; } } return this->sub_tree_cnt[now] = sub_tree_all_cnt; } void bfs(const int root, const int th) { std::queue que; que.emplace(root); while (!que.empty()) { const int now_head = que.front(); que.pop(); for (int now = now_head; now != -1; now = this->heavy[now]) { this->tree_th_num[now] = th; this->vid[now] = pos++; this->inv_vid[this->vid[now]] = now; this->head[now] = now_head; for (auto &&nxt : this->G[now]) { if (nxt != this->parent[now] && nxt != this->heavy[now]) { // not parent && not same heavy path // == different heavy path && haven't search yet que.emplace(nxt); } } } } } // node(vertex) func in [l, r] !!!!! void for_each_node(int a, int b, const std::function &func) { if (this->vid[a] > this->vid[b]) { std::swap(a, b); } func(std::max(this->vid[this->head[b]], this->vid[a]), this->vid[b]); if (this->head[a] != this->head[b]) { this->for_each_node(a, this->parent[this->head[b]], func); } } // edge func in [l, r] !!!!! void for_each_edge(int a, int b, const std::function &func) { if (this->vid[a] > this->vid[b]) { std::swap(a, b); } if (this->head[a] != this->head[b]) { func(this->vid[this->head[b]], this->vid[b]); this->for_each_edge(a, this->parent[this->head[b]], func); } else { if (a != b) { func(this->vid[a] + 1, this->vid[b]); } } } }; const int MAX = 1e5 + 10; RangeAddQuery ra(MAX); HeavyLightDecomposition hld; int n; int main() { scanf("%d", &n); hld = HeavyLightDecomposition(n); for (int i = 0; i < n - 1; i++) { int a, b; scanf("%d%d", &a, &b); a--;b--; hld.add_edge(a, b); } hld.build(); ra.add(0, n, 1); long long ans = 0; int q; scanf("%d", &q); while (q--) { int a, b; scanf("%d%d", &a, &b); a--;b--; hld.for_each_node(a, b, [&](int l, int r) { ans += ra.query(l, r + 1); ra.add(l, r + 1, 1); }); } printf("%lld\n", ans); }