#include using ll = long long; struct Tree { int n, root; std::vector> son; std::vector parent, depth; Tree(const std::vector> &graph, int root = 0) : n(graph.size()), root(root), son(n), parent(n, -1), depth(n, 0) { std::queue que; que.push(root); while (que.size()) { int v = que.front(); que.pop(); for (int c : graph[v]) { if (c == parent[v]) continue; parent[c] = v; son[v].push_back(c); depth[c] = depth[v] + 1; que.push(c); } } } }; class HLD { Tree T; std::vector head, id, id2; int dfs_sz(int v) { int ret = 1, mx_sz = 0; for (int &c : T.son[v]) { int sz = dfs_sz(c); ret += sz; if (mx_sz < sz) { mx_sz = sz; std::swap(T.son[v][0], c); } } return ret; } void dfs_hld(int v, int &k) { id[v] = k++; for (int i = 0; i < T.son[v].size(); i++) { int c = T.son[v][i]; head[c] = (i ? c : head[v]); dfs_hld(c, k); } id2[v] = k; } public: HLD(const Tree &T) : T(T), head(T.n), id(T.n), id2(T.n) { dfs_sz(T.root); int k = 0; dfs_hld(T.root, k); } std::vector get_id() const { return id; } int lca(int u, int v) const { while (head[u] != head[v]) if (T.depth[head[u]] > T.depth[head[v]]) u = T.parent[head[u]]; else v = T.parent[head[v]]; return (T.depth[u] < T.depth[v] ? u : v); } int distance(int u, int v) const { return T.depth[u] + T.depth[v] - T.depth[lca(u, v)] * 2; } // l=lca(u,v) とした時、[u,l] パスと [v,l] パス を閉区間の組みで返す using Interval = std::pair; using Path = std::vector; std::pair path(int u, int v) const { Path path_u, path_v; while (head[u] != head[v]) if (T.depth[head[u]] < T.depth[head[v]]) { path_v.emplace_back(id[v], id[head[v]]); v = T.parent[head[v]]; } else { path_u.emplace_back(id[u], id[head[u]]); u = T.parent[head[u]]; } if (u == v) path_u.emplace_back(id[u], id[u]); else { if (T.depth[u] < T.depth[v]) path_v.emplace_back(id[v], id[u]); else path_u.emplace_back(id[u], id[v]); } return {path_u, path_v}; } // [l,r) が v の部分木 Interval subtree(int v) const { return {id[v], id2[v]}; } }; template class Imos { std::vector data; public: Imos(int n) : data(n, 0) {} //[l,r) に a を追加 void add(int l, int r, T a = 1) { data[l] += a; if (r < data.size()) data[r] -= a; } std::vector build() { for (int i = 0; i + 1 < data.size(); i++) data[i + 1] += data[i]; return data; } }; int main() { int n; std::cin >> n; std::vector> g(n); for (int _ = 1; _ < n; _++) { int u, v; std::cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } Tree t(g); HLD hld(t); Imos imos(n); int q; std::cin >> q; while (q--) { int u, v; std::cin >> u >> v; u--, v--; auto [path_l, path_r] = hld.path(u, v); path_l.insert(path_l.end(), path_r.begin(), path_r.end()); for (const auto [u, v] : path_l) { auto [l, r] = std::minmax(u, v); imos.add(l, r + 1); } } auto sum = imos.build(); ll ans = 0; for (ll x : sum) ans += x * (x + 1) / 2; std::cout << ans << std::endl; }