#include #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(a);i>=(b);i--) #define pb push_back #define pcnt __builtin_popcount #define show(x) cout<<#x<<" = "< pii; typedef vector vi; typedef vector vvi; typedef vector vpii; typedef set si; typedef pair pll; typedef vector vl; typedef vector vvl; typedef vector vpll; typedef set sl; typedef __int128_t lll; typedef pair plll; typedef vector vlll; templatestring join(vector&v) {stringstream s;FOR(i,0,sz(v))s<<' '<b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;} int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;} void dout(double d){printf("%.12f\n",d);} const int iinf = 1e9; const ll linf = 1e18; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-10; const int N = 200005; struct HL{ int root; vi head, heavy, weight, parent, sid; vvi *G, pl; map hid; void dfs(int pos, int pre){ weight[pos] = 1; heavy[pos] = -1; parent[pos] = pre; head[pos] = pos; int mw = 0, w; each(itr, (*G)[pos]){ if(pre == *itr) continue; dfs(*itr, pos); w = weight[*itr]; if(w > mw) mw = w, heavy[pos] = *itr; weight[pos] += w; } } void set_head(int pos, int pre){ if(pos == head[pos]) hid[pos] = sz(hid)-1; pl[head[pos]].pb(pos); each(itr, (*G)[pos]){ if(pre == *itr) continue; if(heavy[pos] == *itr){ head[*itr] = head[pos]; sid[*itr] = sid[pos] + 1; } set_head(*itr, pos); } } struct LCA{ int ln; vvi *G, parent; vi depth; void dfs(int pos, int pre, int d){ depth[pos] = d; each(itr, (*G)[pos]){ if(pre == *itr) continue; parent[0][*itr] = pos; dfs(*itr, pos, d+1); } } int root(int a, int b){ if(depth[a] > depth[b]) swap(a, b); int d = depth[b] - depth[a]; FOR(i, 0, ln) if((1<G = G; int n = sz(*G); for(ln = 0; (1< path(int root, int leaf){ // [root, leaf] => head_id, is_last, idx_l, idx_r if(head[root] == head[leaf]) return mp(mp(hid[head[root]], -1), mp(sid[root], sid[leaf])); return mp(mp(hid[head[leaf]], parent[head[leaf]]), mp(sid[head[leaf]], sid[leaf])); } void build(vvi* G, int r){ this->G = G; lca.build(G, r); int n = sz(*G); head = vi(n); heavy = vi(n); weight = vi(n); parent = vi(n); sid = vi(n); pl = vvi(n); dfs(r, -1); set_head(r, -1); } }; struct StarrySky{ typedef ll T1; typedef ll T2; const T1 e_merge = 0; const T2 e_add = 0; T1 merge(T1 a, T1 b){ return a+b; } T1 addT1(T1 a, int k, int l, int r, T2 b){ return a+b*(r-l); } T2 addT2(T2 a, T2 b){ return a+b; } //################################################### int n; vector d; vector s; void init(int m){ n = 1<<(32-__builtin_clz(m-1)); d.resize(2*n-1); s.resize(2*n-1); fill(d.begin(), d.end(), e_merge); fill(s.begin(), s.end(), e_add); } void init(vector&v){ init(v.size()); for(int j=0; j=0; j--) d[j] = merge(d[j*2+1], d[j*2+2]); } void ref(int k, int l, int r){ if(s[k] != e_add){ int mid = (l+r)/2, _k = k*2+1; s[_k] = addT2(s[_k], s[k]); d[_k] = addT1(d[_k], _k, l, mid, s[k]); _k++; s[_k] = addT2(s[_k], s[k]); d[_k] = addT1(d[_k], _k, mid, r, s[k]); s[k] = e_add; } } T1 _section_add(int a,int b,int k,int l,int r, T2&v){ if(r<=a||b<=l){ }else if(a<=l&&r<=b){ s[k] = addT2(s[k], v); d[k] = addT1(d[k], k, l, r, v); }else{ ref(k, l, r); d[k] = merge(_section_add(a, b, k*2+1, l, (l+r)/2, v), _section_add(a, b, k*2+2, (l+r)/2, r, v)); } return d[k]; } void section_add(int a, int b, T2 v){ _section_add(a, b, 0, 0, n, v); } T1 _query(int a,int b,int k,int l,int r){ if(r<=a||b<=l) return e_merge; if(a<=l&&r<=b) return d[k]; ref(k, l, r); return merge(_query(a, b, k*2+1, l, (l+r)/2), _query(a, b, k*2+2, (l+r)/2, r)); } T1 query(int a,int b){ return _query(a, b, 0, 0, n); } }; StarrySky vss[100005]; HL hl; int n, q, x, y; vvi G; main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n; G.resize(n); FOR(i, 0, n-1){ int a, b; cin >> a >> b; a--; b--; G[a].pb(b); G[b].pb(a); } hl.build(&G, 0); // show(sz(vss)); each(itr, hl.hid){ // show(itr->fi); // show(itr->se); // vl s = vl(sz(hl.pl[itr->fi])); vl s; vss[itr->se].init(s); } return 0; cin >> q; pair t; ll ans = 0; FOR(i, 0, q){ cin >> x >> y; x--; y--; int r = hl.lca.root(x, y); while(true){ t = hl.path(r, x); vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1); ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1); if(t.fi.se == -1) break; x = t.fi.se; } while(true){ t = hl.path(r, y); vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1); ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1); if(t.fi.se == -1) break; y = t.fi.se; } t = hl.path(r, r); ans -= vss[t.fi.fi].query(t.se.fi, t.se.se+1); vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, -1); } cout << ans << endl; return 0; }