#include #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; struct segtree { vector dat, lazy; int n; lli unit = 0; segtree(int N) { n = 1; while (N > n) { n *= 2; } dat.assign(2 * n - 1, unit); lazy.assign(2 * n - 1, unit); } void eval(int k) { if (lazy[k] == 0) return; dat[k] += lazy[k]; if (n - 1 > k) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } lazy[k] = 0; } void update(int a, lli x) { add(a, a + 1, x, 0, 0, n); } void add(int a, int b, lli x) { add(a, b, x, 0, 0, n); } void add(int a, int b, lli x, int k, int l, int r) { eval(k); if (b <= l || r <= a) return; if (a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k); } else { add(a, b, x, 2 * k + 1, l, (l + r) / 2); add(a, b, x, 2 * k + 2, (l + r) / 2, r); dat[k] = dat[2 * k + 1] + dat[2 * k + 2]; } } lli query(int a, int b, int k, int l, int r) { eval(k); if (b <= l || r <= a) return 0; if (a <= l and r <= b) return dat[k]; lli vl = query(a, b, 2 * k + 1, l, (l + r) / 2); lli vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } lli query(int a, int b) { return query(a, b, 0, 0, n); } }; struct hldec { using T = lli; int n; int col = 0; vector> e; vector> heavy; vector> light; vector> cls; vector vers; vector> pos; vector> par; map, int> dict; bool builded = false; vector vec_seg; int root = 0; T unit = 0; vector size; T f(T a, T b) { return a + b; } //add hldec(int n, vector vers, int root = 0) : n(n), root(root), vers(vers) { e.assign(n, {}); par.assign(n, make_pair(-1, -1)); heavy.assign(n, {}); light.assign(n, {}); size.assign(n, 0); pos.assign(n, make_pair(-1, -1)); cls.assign(n, {}); } void add(int u, int v) { e[u].push_back(v); e[v].push_back(u); } int sub_tree_size(int cur, int par) { int tmp = 1; for (auto s : e[cur]) { if (par != s) { tmp += sub_tree_size(s, cur); } } size[cur] = tmp; return tmp; } void dfs_label(int cur, int par) { lli idx = -1; lli mem = 0; rep(i, e[cur].size()) { auto s = e[cur][i]; if (s != par) { if (size[s] > mem) { mem = size[s]; idx = i; } } } if (idx == -1) return; rep(i, e[cur].size()) { auto s = e[cur][i]; if (s != par) { if (idx == i) { heavy[cur].push_back(s); } else { light[cur].push_back(s); } dfs_label(s, cur); } } } void edge_labeling() { sub_tree_size(root, -1); dfs_label(root, -1); } void dfs_arrays(int cur, int c) { cls[c].push_back(vers[cur]); int idx = cls[c].size() - 1; pos[cur] = make_pair(c, cls[c].size() - 1); dict[pos[cur]] = cur; for (auto s : heavy[cur]) { dfs_arrays(s, c); } for (auto s : light[cur]) { col++; par[col] = make_pair(c, idx); dfs_arrays(s, col); } } void make_arrays() { dfs_arrays(root, 0); } void build_segtree() { rep(j, cls.size()) { auto& s = cls[j]; int size = s.size(); segtree seg(size); rep(i, size) { seg.update(i, s[i]); } vec_seg.push_back(seg); } } void build(bool opt = false) { edge_labeling(); if (opt) { e.clear(); } cerr << "labeled done" << endl; make_arrays(); cerr << "arrays" << endl; if (opt) { heavy.clear(); light.clear(); } build_segtree(); builded = true; cerr << "seg_build" << endl; } void add(int u, int v, T x) { if (!builded) { cout << "HOGE" << endl; build(); builded = true; } vector> hist_u; vector> hist_v; rep(j, 2) { int tmp = j == 1 ? u : v; while (true) { int cur_col = pos[tmp].first; if (j) hist_u.push_back(pos[tmp]); else hist_v.push_back(pos[tmp]); if (cur_col == 0) break; tmp = dict[par[cur_col]]; } } int pivot = 0; T ans = unit; set hist_u_set; map post; for (auto s : hist_u) { hist_u_set.insert(s.first); post[s.first] = s.second; } rep(i, hist_v.size()) { if (hist_u_set.find(hist_v[i].first) != hist_u_set.end()) { int h = post[hist_v[i].first]; vec_seg[hist_v[i].first].add(min(h, hist_v[i].second), max(h, hist_v[i].second) + 1, x); pivot = hist_v[i].first; break; } } rep(i, hist_u.size()) { if (hist_u[i].first == pivot) break; vec_seg[hist_u[i].first].add(0, hist_u[i].second + 1, x); } rep(i, hist_v.size()) { if (hist_v[i].first == pivot) break; vec_seg[hist_v[i].first].add(0, hist_v[i].second + 1, x); } } T query(int u, int v) { if (!builded) { build(); builded = true; } vector> hist_u; vector> hist_v; rep(j, 2) { int tmp = j == 1 ? u : v; while (true) { int cur_col = pos[tmp].first; if (j) hist_u.push_back(pos[tmp]); else hist_v.push_back(pos[tmp]); if (cur_col == 0) break; tmp = dict[par[cur_col]]; } } int pivot = 0; T ans = unit; set hist_u_set; map post; for (auto s : hist_u) { hist_u_set.insert(s.first); post[s.first] = s.second; } rep(i, hist_v.size()) { if (hist_u_set.find(hist_v[i].first) != hist_u_set.end()) { int h = post[hist_v[i].first]; ans = f(vec_seg[hist_v[i].first].query(min(h, hist_v[i].second), max(h, hist_v[i].second) + 1), ans); pivot = hist_v[i].first; break; } } rep(i, hist_u.size()) { if (hist_u[i].first == pivot) break; ans = f(vec_seg[hist_u[i].first].query(0, hist_u[i].second + 1), ans); } rep(i, hist_v.size()) { if (hist_v[i].first == pivot) break; ans = f(vec_seg[hist_v[i].first].query(0, hist_v[i].second + 1), ans); } return ans; } }; int main() { int n, m; cin >> n; vector v(n, 0); hldec tr(n, v); rep(i, n - 1) { int u, v; cin >> u >> v, u--, v--; tr.add(u, v); } int q; tr.build(true); cin >> q; lli sum = 0; rep(i, q) { int u, v; cin >> u >> v, u--, v--; tr.add(u, v, 1); sum += tr.query(u, v); } cout << sum << endl; // //cout << tr.query(0,1)<