# include # include #include # include #include #include #include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include # include #include #include #include #include #include #include //#include using namespace std; using LL = long long; using ULL = unsigned long long; long long MOD = 1000000000 + 7;// 998244353;// ; constexpr long long INF = numeric_limits::max() / 2; const double PI = acos(-1); #define fir first #define sec second #define thi third #define debug(x) cerr<<#x<<": "< Pll; typedef pair> Ppll; typedef pair>> Pbll; typedef pair>> Pvll; typedef pair Vec2; struct Tll { LL first, second, third; }; struct Fll { LL first, second, third, fourd; }; typedef pair Ptll; #define rep(i,rept) for(LL i=0;i=0;i--) void YN(bool f) { if (f) cout << "YES" << endl; else cout << "NO" << endl; } void yn(bool f) { if (f) cout << "Yes" << endl; else cout << "No" << endl; } struct Edge { LL to, cost; }; struct edge { LL from, to, cost; }; vector>g,rev; vectoredges; vectorv[510000]; mapma; setst; LL h, w, n, m, k, t, s, p, q, last, cnt, sum, ans, a[510000], b[510000]; mapdp; string str, ss; bool f; char c; struct Seg { LL n; vectornode, lazy; Seg(vectorv) { n = 1; while (n < v.size())n *= 2; node.resize(n * 2 - 1); lazy.resize(n * 2 - 1); rep(i, n)node[n + i - 1] = v[i]; Rrep(i, n - 2)node[i] = min(node[i * 2 + 1], node[i * 2 + 2]); //rep(i, n * 2 - 1)lazy[i] = -1; } Seg(LL n_) { n = 1; while (n < n_)n *= 2; node.resize(n * 2 - 1); lazy.resize(n * 2 - 1); rep(i, n)node[n + i - 1] = 0; Rrep(i, n - 2)node[i] = min(node[i * 2 + 1], node[i * 2 + 2]); //区間最小などの時 //rep(i, n * 2 - 1)lazy[i] = -1; } //区間の和の遅延 void eval(LL k, LL l, LL r) { if (lazy[k] != 0) { node[k] += lazy[k]; if (r - l >= 1) { lazy[k * 2 + 1] += lazy[k] / 2; lazy[k * 2 + 2] += lazy[k] / 2; } lazy[k] = 0; } } //区間の最小の遅延 void ceval(LL k, LL l, LL r) { if (lazy[k] != -1) { node[k] = lazy[k]; if (r - l >= 1) { lazy[k * 2 + 1] = lazy[k]; lazy[k * 2 + 2] = lazy[k]; } lazy[k] = -1; } } void update(LL i, LL x) { i = i + n - 1; node[i] = x; while (i > 0) { i = (i - 1) / 2; node[i] = min(node[i * 2 + 1], node[i * 2 + 2]); } } void update(LL i, LL x, LL a, LL b, LL l, LL r) { //ceval(i, a, b); if (b < l || r < a)return; if (l <= a && b <= r) { lazy[i] = x; ceval(i, a, b); } else { update(i * 2 + 1, x, a, (a + b) / 2, l, r); update(i * 2 + 2, x, (a + b + 1) / 2, b, l, r); node[i] = min(node[i * 2 + 1], node[i * 2 + 2]); } } LL find(LL i, LL a, LL b, LL l, LL r) { ceval(i, a, b); if (b < l || r < a)return INF; if (l <= a && b <= r)return node[i]; return min(find(i * 2 + 1, a, (a + b) / 2, l, r), find(i * 2 + 2, (a + b + 1) / 2, b, l, r)); } void add(LL i, LL x) { i = i + n - 1; node[i] += x; while (i > 0) { i = (i - 1) / 2; node[i] = (node[i * 2 + 1] + node[i * 2 + 2]); } } void add(LL i, LL x, LL a, LL b, LL l, LL r) { eval(i, a, b); if (b < l || r < a)return; if (l <= a && b <= r) { lazy[i] += (b - a + 1)*x; eval(i, a, b); } else { add(i * 2 + 1, x, a, (a + b) / 2, l, r); add(i * 2 + 2, x, (a + b + 1) / 2, b, l, r); node[i] = node[i * 2 + 1] + node[i * 2 + 2]; } } LL getsum(LL i, LL a, LL b, LL l, LL r) { eval(i, a, b); if (b < l || r < a)return 0; if (l <= a && b <= r)return node[i]; return (getsum(i * 2 + 1, a, (a + b) / 2, l, r) + getsum(i * 2 + 2, (a + b + 1) / 2, b, l, r)); } }; Seg seg(200000); struct HLD { LL n, pos; vector > G; vector vid, head, m_dep, hvy, par, dep, inv, type; HLD() {} HLD(LL sz) : n(sz), pos(0), G(n), vid(n, -1), head(n), m_dep(n, -1), hvy(n, -1), par(n), dep(n), inv(n), type(n) {} void add_edge(LL u, LL v) { G[u].push_back(v); G[v].push_back(u); } void build(vector rs = vector(1, 0)) { LL c = 0; for (LL r : rs) { dfs(r); bfs(r, c++); } } void dfs(LL rt) { using T = pair; stack st; par[rt] = -1; dep[rt] = 0; st.emplace(rt, 0); while (!st.empty()) { LL v = st.top().first; LL &i = st.top().second; if (i < (LL)G[v].size()) { LL u = G[v][i++]; if (u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.emplace(u, 0); } else { st.pop(); LL res = 0; for (LL u : G[v]) { if (u == par[v]) continue; m_dep[v] = max(m_dep[v], m_dep[u] + 1); if (res < m_dep[u]) res = m_dep[u], hvy[v] = u; } } } } void bfs(LL r, LL c) { LL &k = pos; queue q({ r }); while (!q.empty()) { LL h = q.front(); q.pop(); for (LL i = h; i != -1; i = hvy[i]) { type[i] = c; vid[i] = k++; inv[vid[i]] = i; head[i] = h; for (LL j : G[i]) if (j != par[i] && j != hvy[i]) q.push(j); } } } // for_each(vertex) // [l,r] <- attention!!, const function& f void for_each(LL u, LL v, LL x) { while (1) { if (vid[u] > vid[v]) swap(u, v); seg.add(0, x, 0, seg.n - 1, max(vid[head[v]], vid[u]), vid[v]); ans += seg.getsum(0, 0, seg.n - 1, max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) v = par[head[v]]; else break; } } // for_each(edge) // [l,r] <- attention!! void for_each_edge(LL u, LL v, const function& f) { while (1) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { f(vid[head[v]], vid[v]); v = par[head[v]]; } else { if (u != v) f(vid[u] + 1, vid[v]); break; } } } LL lca(LL u, LL v) { while (1) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } LL distance(LL u, LL v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; int main() { cin >> n; HLD hl(n); rep(i, n - 1) { LL x, y; cin >> x >> y; hl.add_edge(x - 1, y - 1); } hl.build(); cin >> q; rep(i, q) { int x, y; cin >> x >> y; hl.for_each(x - 1, y - 1, 1); } cout << ans << endl; return 0; }