# 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; constexpr long long MOD = 1000000000 + 7; constexpr long long INF = std::numeric_limits::max(); const double PI = acos(-1); #define fir first #define sec second typedef pair Pll; typedef pair> Ppll; typedef pair>> Pbll; typedef pair>> Pvll; typedef pair Vec2; struct Tll { LL first, second, third; }; typedef pair Ptll; #define rep(i,rept) for(LL i=0;i=0;i--) int h, w, n, m, k, s, t, q, ans, sum, last, cnt; struct Edge { int to,cost; }; string str; bool f; 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 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]; Mfor(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; Mfor(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 { int n, pos; vector > G; vector vid, head, sub, hvy, par, dep, inv, type; HLD() {} HLD(int sz) : n(sz), pos(0), G(n), vid(n, -1), head(n), sub(n, 1), hvy(n, -1), par(n), dep(n), inv(n), type(n) {} void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u); } void build(vector rs = vector(1, 0)) { int c = 0; for (int r : rs) { dfs(r); bfs(r, c++); } } void dfs(int rt) { using T = pair; stack st; par[rt] = -1; dep[rt] = 0; st.emplace(rt, 0); while (!st.empty()) { int v = st.top().first; int &i = st.top().second; if (i<(int)G[v].size()) { int u = G[v][i++]; if (u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.emplace(u, 0); } else { st.pop(); int res = 0; for (int u : G[v]) { if (u == par[v]) continue; sub[v] += sub[u]; if (res q({ r }); while (!q.empty()) { int h = q.front(); q.pop(); for (int i = h; i != -1; i = hvy[i]) { type[i] = c; vid[i] = k++; inv[vid[i]] = i; head[i] = h; for (int 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(int u, int v, int 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(int u, int 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; } } } int lca(int u, int v) { while (1) { if (vid[u]>vid[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; int main() { cin >> n; HLD hl(n); rep(i, n-1) { int 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; }