#include #include #define rep(i,n) for(int i=0;i vi; typedef vector vl; typedef vector> vvi; typedef vector> vvl; typedef long double ld; typedef pair P; template ostream& operator<<(ostream& os, const static_modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const dynamic_modint& a) {os << a.val(); return os;} template istream& operator>>(istream& is, static_modint& a) {long long x; is >> x; a = x; return is;} template istream& operator>>(istream& is, dynamic_modint& a) {long long x; is >> x; a = x; return is;} template istream& operator>>(istream& is, vector& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template ostream& operator<<(ostream& os, const pair& p){os << p.first << ' ' << p.second; return os;} template ostream& operator<<(ostream& os, const vector& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const vector>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template ostream& operator<<(ostream& os, const set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const unordered_set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const atcoder::segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const atcoder::lazy_segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template void chmin(T& a, T b){a = min(a, b);} template void chmax(T& a, T b){a = max(a, b);} // Lowest Common Ancestor by binary lifting // https://youtu.be/8uowVvQ_-Mo?t=4306 template // T: type of cost struct lca { int n, root, l; vector> to; vector> co; vector dep; vector costs; vector> par; lca(int n):n(n),to(n),co(n),dep(n),costs(n) { l = 0; while ((1<>(n+1,vector(l,n)); } void addEdge(int a, int b, T c=0) { to[a].push_back(b); co[a].push_back(c); to[b].push_back(a); co[b].push_back(c); } void dfs(int v, int d=0, T c=0, int p=-1) { if (p != -1) par[v][0] = p; dep[v] = d; costs[v] = c; for (int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if (u == p) continue; dfs(u, d+1, c+co[v][i], v); } } void init(int _root=0) { root = _root; dfs(root); for (int i = 0; i < l-1; ++i) { for (int v = 0; v < n; ++v) { par[v][i+1] = par[par[v][i]][i]; } } } // LCA int up(int v, int k) { for (int i = l-1; i >= 0; --i) { int len = 1<= len) k -= len, v = par[v][i]; } return v; } int operator()(int a, int b) { if (dep[a] > dep[b]) swap(a,b); b = up(b, dep[b]-dep[a]); if (a == b) return a; for (int i = l-1; i >= 0; --i) { int na = par[a][i], nb = par[b][i]; if (na != nb) a = na, b = nb; } return par[a][0]; } int length(int a, int b) { int c = (*this)(a,b); return dep[a]+dep[b]-dep[c]*2; } T dist(int a, int b) { int c = (*this)(a,b); return costs[a]+costs[b]-costs[c]*2; } }; using S = long long; S op(S a, S b){ return a + b; } S e(){ return 0LL; } int main(){ int n; cin >> n; vector> G(n); lca lca_graph(n); rep(i, n - 1){ int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); lca_graph.addEdge(u, v); } lca_graph.init(); vector> children(n); vector sz(n); vector parent(n, -1); auto dfs_sz = [&](auto self, int from, int prev) -> int{ int res = 1; for(int to : G[from]){ if(to == prev) continue; children[from].push_back(to); parent[to] = from; res += self(self, to, from); } return sz[from] = res; }; dfs_sz(dfs_sz, 0, -1); vector belong_major(n, -1); vector belong_minor(n, -1); vector parent_light(n, -1); vector length(n); vector> seg; auto dfs_decompose = [&](auto self, int from, int prev) -> void{ sort(children[from].begin(), children[from].end(), [&](int u, int v){ return sz[u] > sz[v]; }); if(children[from].size()){ // heavy edge { int to = children[from][0]; parent_light[to] = prev; belong_major[to] = belong_major[from]; belong_minor[to] = belong_minor[from] + 1; length[belong_major[to]]++; self(self, to, prev); } // light edge for(int dir = 1; dir < int(children[from].size()); dir++){ int to = children[from][dir]; parent_light[to] = from; belong_major[to] = to; belong_minor[to] = 0; length[belong_major[to]]++; self(self, to, from); } } }; belong_major[0] = 0; belong_minor[0] = 0; length[0] = 1; dfs_decompose(dfs_decompose, 0, -1); rep(i, n){ vector init(length[i], 0LL); seg.emplace_back(init); } int q; cin >> q; auto add = [&](auto self, int x, long long c = 1) -> void{ if(x == -1) return; int idx_major = belong_major[x]; int idx_minor = belong_minor[x]; { long long val = seg[idx_major].get(0); seg[idx_major].set(0, val + c); } if(idx_minor + 1 < length[idx_major]){ long long val = seg[idx_major].get(idx_minor + 1); seg[idx_major].set(idx_minor + 1, val - c); } self(self, parent_light[x], c); }; rep(_, q){ int a, b; cin >> a >> b; a--; b--; add(add, a, 1); add(add, b, 1); int c = lca_graph(a, b); add(add, c, -1); add(add, parent[c], -1); } auto c2 = [&](long long x){return x * (x + 1) / 2;}; long long ans = 0; auto dfs_calc = [&](auto self, int from, long long val) -> void{ int idx_major = belong_major[from]; int idx_minor = belong_minor[from]; val += seg[idx_major].get(idx_minor); ans += c2(val); if(children[from].size()){ // heavy edge { int to = children[from][0]; self(self, to, val); } // light edge for(int dir = 1; dir < int(children[from].size()); dir++){ int to = children[from][dir]; self(self, to, 0LL); } } }; dfs_calc(dfs_calc, 0, 0LL); cout << ans << "\n"; return 0; }