#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include using namespace std; template struct BIT{ int n; vector bit[2]; BIT(int n_){init(n_);} void init(int n_){ n=n_+1; for(int p=0;p < 2;p++) bit[p].assign(n,0); } void add_sub(int p,int i,T x){ for(int idx=i;idx0;idx-=(idx & -idx)){ s+=bit[p][idx]; } return s; } T sum(int i){return sum_sub(0,i)+sum_sub(1,i)*i;} T sum(int i,int j){ //[i,j]の要素の総和 return sum(j)-sum(i-1); } }; typedef vector > Graph; struct HLDecomposition { int n; Graph G; vector vid, inv, par, depth, subsize, head, next, type; // construct HLDecomposition() { } HLDecomposition(const Graph &G_) : n((int)G_.size()), G(G_), vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1), head(n), next(n, -1), type(n) { } void build(vector roots = {0}) { int curtype = 0, pos = 0; for (auto r : roots) dfs(r), bfs(r, curtype++, pos); } void dfs(int r) { stack > st; par[r] = -1, depth[r] = 0; st.emplace(r, 0); while (!st.empty()) { int v = st.top().first; int &i = st.top().second; if (i < (int)G[v].size()) { int e = G[v][i++]; if (e == par[v]) continue; par[e] = v, depth[e] = depth[v] + 1; st.emplace(e, 0); } else { st.pop(); int maxsize = 0; for (auto e : G[v]) { if (e == par[v]) continue; subsize[v] += subsize[e]; if (maxsize < subsize[e]) maxsize = subsize[e], next[v] = e; } } } } void bfs(int r, int curtype, int &pos) { queue que({r}); while (!que.empty()) { int start = que.front(); que.pop(); for (int v = start; v != -1; v = next[v]) { type[v] = curtype; vid[v] = pos++; inv[vid[v]] = v; head[v] = start; for (auto e : G[v]) if (e != par[v] && e != next[v]) que.push(e); } } } // node query [u, v], f([left, right]) void foreach_nodes(int u, int v, const function &f) { while (true) { if (vid[u] > vid[v]) swap(u, v); f(max(vid[head[v]], vid[u]), vid[v]); if (head[u] != head[v]) v = par[head[v]]; else break; } } // edge query [u, v], f([left, right]) void foreach_edges(int u, int v, const function &f) { while (true) { 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; } } } // LCA int lca(int u, int v) { while (true) { if (vid[u] > vid[v]) swap(u, v); if (head[u] == head[v]) return u; v = par[head[v]]; } } }; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin>>n; Graph G(n); rep(i,n-1){ int u,v; cin>>u>>v; u--,v--; G[u].push_back(v); G[v].push_back(u); } HLDecomposition hld(G); hld.build(); BIT bit(n); int q; cin>>q; ll ans=0; rep(i,q){ int a,b; cin>>a>>b; a--,b--; hld.foreach_nodes(a,b,[&](int l,int r){ bit.add(l+1,r+1,1); ans+=bit.sum(l+1,r+1); }); } cout<