#include using namespace std; using ll = long long; template struct LazySegTree { using FX = function;//Xに作用素Mを作用させる int n; int siz; FX fx; vector dat; vector lazy; LazySegTree(){} LazySegTree(int _siz, FX _fx) : siz(_siz), fx(_fx) { n = 1; while(n < siz) n <<= 1; dat.assign(n * 2, X::ide()); lazy.assign(n * 2, E::ide()); } private: void eval(int k, int len) { if(lazy[k] == E::ide()) return; if(k < n) { lazy[k<<1] = op(lazy[k<<1], lazy[k]); lazy[k<<1|1] = op(lazy[k<<1|1], lazy[k]); } dat[k] = fx(dat[k], lazy[k], len); lazy[k] = E::ide(); } X query(int a, int b, int l, int r, int k) { eval(k,r-l); if(r <= a || b <= l) return X::ide(); if(a <= l && r <= b) return dat[k]; int mid = (l + r)>>1; X L = query(a, b, l, mid, k<<1); X R = query(a, b, mid, r, k<<1|1); return op(L, R); } void update(int a, int b, E m, int l, int r, int k) {//[a, b) := クエリ区間 [l, r) := 今見ている区間 eval(k, r-l); if(r <= a || b <= l) return; if(a <= l && r <= b) { lazy[k] = op(lazy[k], m); eval(k, r-l); } else { int mid = (l + r)>>1; update(a, b, m, l, mid, k<<1); update(a, b, m, mid, r, k<<1|1); dat[k] = op(dat[k<<1], dat[k<<1|1]); } } public: void set(int i, X x) { dat[i + n - 1] = x; } void init() { for(int i = n-1; i >= 1; i--) { dat[i] = op(dat[i*2], dat[i * 2 + 1]); } } void change(int l, int r, E m) { update(l, r + 1, m, 1, n + 1, 1); } X get(int l, int r) { return query(l, r + 1, 1, n + 1, 1); } void dump() { for(int i = 1; i <= siz; i++) { cout << get(i, i) << " ";//適宜直す。 } cout << endl; } }; template struct HLD { vector siz;//[元の頂点番号] = サイズ vector num;//[元の頂点番号] = 振り直した頂点番号 vector numrev; vector out;//[元の頂点番号] = new 半開区間で、その頂点を出た時の値 + 1 vector par;//[振られた] = 振られた 自分の親 vector head;//[振られた番号] = 振られた番号 自分の連結成分の頭 LazySegTree seg; using FX = function; FX fx; int N; int size = 1; HLD(int _N, vector>& G, FX _fx) : N(_N), fx(_fx) { par.resize(N+1); iota(par.begin(), par.end(), 0); siz.resize(N+1, 1); num.assign(N+1, -1); numrev.resize(N+1, -1); out.resize(N+1, -1); head.resize(N+1); seg = LazySegTree(N, fx); auto dfs_siz = [&](auto f, int now, int prev) -> void { int sum = 1; for(int to : G[now]) { if(to == prev) continue; f(f, to, now); sum += siz[to]; } siz[now] = sum; return; }; dfs_siz(dfs_siz, 1, -1); for(int i = 1; i <= N; i++) { sort(G[i].begin(), G[i].end(), [&](int a, int b) { return siz[a] > siz[b]; }); } int idx = 1; auto dfs_bunkai = [&](auto f, int now, int prev, int hed) -> void { num[now] = idx;//番号付 numrev[idx] = now; idx++; par[num[now]] = prev;//親の頂点 //1だけは直前も自分も1 if(hed == -1)hed = num[now]; head[num[now]] = hed; bool flag = true; for(int i = 0; i <= int(G[now].size()) - 1; i++) { if(num[G[now][i]] != -1) continue; if(flag) f(f, G[now][i], num[now], hed), flag = false; else f(f, G[now][i], num[now], -1); } out[now] = idx; return; }; dfs_bunkai(dfs_bunkai, 1, 1, -1); } private: X get__(int u, int v) { int w = num[getLCA(u, v)];//lcaで左右に分ける u = num[u]; v = num[v]; X L = X::ide(), R = X::ide(); while(u != w) { int hed = max(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。 L = op(seg.get(hed, u), L); //根から上の方へ if(hed != w) u = par[hed]; else u = w; } L = op(seg.get(w, w), L);//根から上の方へ while(v != w) { int hed = max(head[v], w+1); R = op(seg.get(hed, v), R); //根から上の方へ if(hed != w) v = par[hed]; else v = w; } return op(L, R);//交換則を要する時はこの行を変更する必要があるかもしれない : 無いと思うがr } void change__(int u, int v, E e) { int w = num[getLCA(u, v)];//lcaで左右に分ける u = num[u]; v = num[v]; while(u != w) { int hed = max(head[u], w+1);//wまで登ると、wを左右で2回カウントしてしまう。 seg.change(hed, u, e); //根から上の方へ if(hed != w) u = par[hed]; else u = w; } seg.change(w, w, e); while(v != w) { int hed = max(head[v], w+1); seg.change(hed, v, e); if(hed != w) v = par[hed]; else v = w; } } public: void set(int pos, X x) { pos = num[pos]; seg.set(pos, x); } void init() { seg.init(); } void change(int u, int v, E e) { change__(u, v, e); } X get(int u, int v) { return get__(u, v); } X subtree(int v) { int l = num[v]; int r = out[v] - 1; return seg.get(l, r); } int getLCA(int a, int b) {//入 : 元番号 出 : 元番号 a = num[a]; b = num[b]; while(true) { if(a > b) swap(a, b); if(head[a] == head[b]) return numrev[a]; b = par[head[b]]; } } int parent(int a) {//入 : 元番号 return numrev[par[num[a]]]; } /* Brief hld。 HLD hld(N, G) N...max_n G ... graph パスに対するクエリがlog^2 部分木に対するクエリがlog */ }; struct Monoid { ll a; Monoid(){} Monoid(ll _a) : a(_a) { } friend Monoid op(const Monoid& l, const Monoid& r) { return l.a + r.a; } static Monoid ide() { return 0LL; } bool operator==(const Monoid& x) const {return a == x.a;} bool operator!=(const Monoid& x) const {return !(*this == x);} }; struct E { ll a; E(){} E(ll _a) : a(_a) {} friend E op(const E& l, const E& r) {//rのが新しい。(affine) return l.a + r.a; } static E ide() { return 0LL; } bool operator==(const E& x) const {return (a == x.a);} bool operator!=(const E& x) const {return !(*this == x);} }; Monoid fx(const Monoid& l, const E& r, long long len) { return l.a + r.a * len; } int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); int N; cin >> N; vector> G(N+1); for(int i = 1; i < N; i++) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } HLD hld(N, G, fx); for(int i = 1; i <= N; i++) hld.set(i, 1); hld.init(); int Q; cin >> Q; long long ans = 0; while(Q--) { int a, b; cin >> a >> b; ans += hld.get(a, b).a; hld.change(a, b, 1); } cout << ans << endl; }