#include 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].front(), c); } } return ret; } void dfs_hld(int v, int &k) { id[v] = k++; for (int c : T.son[v]) { head[c] = (c == T.son[v].front() ? head[v] : c); 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) { 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) { return T.depth[u] + T.depth[v] - T.depth[lca(u, v)] * 2; } using Interval = std::pair; using Path = std::vector; // 和がuvパスになるような閉区間の組みを返す Path path(int u, int v) { Path path; while (head[u] != head[v]) { if (T.depth[head[u]] > T.depth[head[v]]) std::swap(u, v); path.emplace_back(id[head[v]], id[v]); v = T.parent[head[v]]; } path.emplace_back(std::minmax(id[u], id[v])); return path; } // l=lca(u,v) とした時、[u,l] パスと [v,l] パス を閉区間の組みで返す // 非可換クエリ用 std::pair path_ordered(int u, int v) { 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 (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) { 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; } }; std::vector> scan_graph(int n, int m, int index = 1) { std::vector> g(n); while (m--) { int u, v; std::cin >> u >> v; u -= index, v -= index; g[u].push_back(v); g[v].push_back(u); } return g; } Tree scan_tree(int n, int index = 1) { return Tree(scan_graph(n, n - 1, index)); } using ll = long long; int main() { int n; std::cin >> n; Tree t = scan_tree(n); HLD hld(t); int q; std::cin >> q; Imos imos(n); while (q--) { int u, v; std::cin >> u >> v; u--, v--; auto p = hld.path(u, v); for (const auto &[l, r] : p) 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; }