/*** author: yuji9511 ***/ #include using namespace std; using ll = long long; using lpair = pair; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i void print(H&& h, T&&... t){cout<(t)...);} struct AddLazySegmentTree { private: ll n; vector node, lazy; public: AddLazySegmentTree(vector v) { ll sz = (ll)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1); lazy.resize(2*n-1, 0); for(ll i=0; i=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } void eval(ll k, ll l, ll r) { if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) { lazy[2*k+1] += lazy[k] / 2; lazy[2*k+2] += lazy[k] / 2; } lazy[k] = 0; } } void add(ll a, ll b, ll x, ll k=0, ll l=0, ll r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } else { add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); node[k] = node[2*k+1] + node[2*k+2]; } } ll getsum(ll a, ll b, ll k=0, ll l=0, ll r=-1) { if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2*k+1, l, (l+r)/2); ll vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } }; vector tree[100010]; vector hld; ll pre[100010]; ll A[100010]; ll sz[100010] = {}; ll depth[100010] = {}; ll p[100010]; vector vertex; ll N; void HLD(ll v, ll a , ll par){ vertex.push_back(v); pre[v] = hld.size(); hld.push_back(v); A[v] = a; if(tree[v].size() == 0) return; if(tree[v].size() == 1 && par != -1) return; ll M = 0; ll idx = -1; for(ll i=0; i M){ M = sz[tree[v][i]]; idx = i; } } HLD(tree[v][idx], a, v); for(ll i=0; i query(ll u, ll v){ vector ret; while(A[u] != A[v]){ if(depth[A[u]] <= depth[A[v]]){ ret.push_back({pre[A[v]], pre[v] + 1}); v = p[A[v]]; } else{ ret.push_back({pre[A[u]], pre[u] + 1}); u = p[A[u]]; } } ret.push_back({min(pre[u],pre[v]), max(pre[u], pre[v]) + 1}); return ret; } void dfs(ll cur, ll par, ll d = 0){ depth[cur] = d; sz[cur] = 1; for(auto &e: tree[cur]){ if(e == par) continue; dfs(e, cur, d+1); sz[cur] += sz[e]; } } int main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> N; rep(i,0,N-1){ ll u,v; cin >> u >> v; u--; v--; tree[u].push_back(v); tree[v].push_back(u); } // rep(i,0,N){ // cin >> p[i]; // if(p[i] != -1){ // tree[p[i]].push_back(i); // tree[i].push_back(p[i]); // } // } dfs(0,-1); HLD(0,0,-1); ll Q; cin >> Q; vector v(N+1,0); AddLazySegmentTree sg(v); ll table[100010] = {}; rep(i,0,N) table[vertex[i]] = i; // printa(table, N); while(Q--){ ll a,b; cin >> a >> b; a--; b--; vector q = query(table[a],table[b]); for(auto &e: q){ sg.add(e.first, e.second,1); } } ll ans = 0; // rep(i,0,N) print(sg.getsum(i,i+1)); rep(i,0,N){ ll r = sg.getsum(i,i+1); ans += r * (r+1) / 2; } print(ans); // ll table[100010] = {}; // vector v(N+1,0); // AddLazySegmentTree sg(v); // rep(i,0,N) table[vertex[i]] = i; // rep(i,0,Q){ // ll u,v; // cin >> u >> v; // // print(u,v); // vector ans = query(u,v); // for(auto &e: ans){ // // prll(e.first, e.second); // sg.add(e.first, e.second, 1); // } // } // // rep(i,0,N){ // // ll t = table[i]; // // prll(sg.getsum(t,t+1)); // // } // print(sg.getsum(table[5], table[5]+1)); }