#include #define FOR(v, a, b) for(int v = (a); v < (b); ++v) #define FORE(v, a, b) for(int v = (a); v <= (b); ++v) #define REP(v, n) FOR(v, 0, n) #define REPE(v, n) FORE(v, 0, n) #define REV(v, a, b) for(int v = (a); v >= (b); --v) #define ALL(x) (x).begin(), (x).end() #define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it) #define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it) #define EXIST(c,x) ((c).find(x) != (c).end()) #define LLI long long int #define fst first #define snd second #ifndef M_PI #define M_PI 3.14159265358979323846 #endif #ifndef M_E #define M_E 2.71828182845904523536 #endif #ifdef DEBUG #include #else #define dump(x) #endif #define pln(x) cout << (x) << endl #define gcd __gcd using namespace std; template constexpr T lcm(T m, T n){return m/gcd(m,n)*n;} template using V = vector; template using P = pair; template void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost< istream& operator>>(istream &is, vector &v){for(auto &a : v) is >> a; return is;} template istream& operator>>(istream &is, pair &p){is >> p.first >> p.second; return is;} template T& chmin(T &a, const U &b){return a = (a<=b?a:b);} template T& chmax(T &a, const U &b){return a = (a>=b?a:b);} template void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);} template class Edge{ public: int from,to; Cost cost; Edge() {} Edge(int to, Cost cost): to(to), cost(cost){} Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){} Edge rev(){return Edge(to,from,cost);} static bool cmp_to_lt(const Edge &e1, const Edge &e2){return e1.to < e2.to;} static bool cmp_cost_lt(const Edge &e1, const Edge &e2){return e1.cost < e2.cost;} static bool cmp_to_gt(const Edge &e1, const Edge &e2){return e1.to > e2.to;} static bool cmp_cost_gt(const Edge &e1, const Edge &e2){return e1.cost > e2.cost;} friend ostream& operator<<(ostream &os, const Edge &e){ os << "(FROM: " << e.from << "," << "TO: " << e.to << "," << "COST: " << e.cost << ")"; return os; } }; template using Tree = vector>>; template class RangeRangeSegmentTree{ int size; T e1; vector vec1; function f1; U e2; vector vec2; function f2; function g; void propagate(int i, int l){ if(vec2[i] == e2) return; if(i < size/2){ vec2[i*2+1] = f2(vec2[i], vec2[i*2+1]); vec2[i*2+2] = f2(vec2[i], vec2[i*2+2]); } vec1[i] = g(vec1[i], vec2[i], l); vec2[i] = e2; } T update_aux(int i, int l, int r, int s, int t, const U &x){ propagate(i,r-l); if(r <= s || t <= l) return vec1[i]; else if(s <= l && r <= t){ vec2[i] = f2(vec2[i],x); propagate(i,r-l); return vec1[i]; } else return vec1[i] = f1(update_aux(i*2+1,l,(l+r)/2,s,t,x), update_aux(i*2+2,(l+r)/2,r,s,t,x)); } T query_aux(int i, int l, int r, int x, int y){ propagate(i,r-l); if(r <= x || y <= l) return e1; else if(x <= l && r <= y) return vec1[i]; else return f1(query_aux(i*2+1,l,(l+r)/2,x,y), query_aux(i*2+2,(l+r)/2,r,x,y)); } public: RangeRangeSegmentTree(){} RangeRangeSegmentTree(int n, const T &e1, const function f1, const U &e2, const function f2, const function g): e1(e1), f1(f1), e2(e2), f2(f2), g(g){ size = 1; while(size(size,e1); vec2 = vector(size,e2); } void update(int s, int t, const U &x){ update_aux(0,0,size/2+1,s,t,x); } T query(int x, int y){ return query_aux(0,0,size/2+1,x,y); } }; template class HLDecomposition{ Tree tree; int n; vector sub, par, head, id, rid, next; int dfs_sub(int cur, int p){ par[cur] = p; int t = 0; for(auto &e : tree[cur]){ if(e.to == p) continue; sub[cur] += dfs_sub(e.to, cur); if(sub[e.to] > t){ t = sub[e.to]; next[cur] = e.to; swap(e, tree[cur][0]); } } return sub[cur]; } int dfs_build(int cur, int &i){ id[cur] = i; rid[i] = cur; ++i; for(auto &e : tree[cur]){ if(e.to == par[cur]) continue; head[e.to] = (e.to == tree[cur][0].to ? head[cur] : e.to); dfs_build(e.to, i); } } public: HLDecomposition(const Tree &tree): tree(tree), n(tree.size()), sub(n,1), next(n,-1), head(n), par(n,-1), id(n), rid(n){ dfs_sub(0, -1); int i=0; dfs_build(0, i); } void path_query_vertex(int x, int y, const function &f){ while(1){ if(id[x] > id[y]) swap(x, y); f(max(id[head[y]], id[x]), id[y]); if(head[x] == head[y]) return; y = par[head[y]]; } } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int N; while(cin >> N){ Tree tree(N); REP(i,N-1){ int u,v; cin >> u >> v; --u, --v; tree[u].push_back(Edge(u,v,1)); tree[v].push_back(Edge(v,u,1)); } auto f = [](LLI a, LLI b){return a+b;}; auto g = [](LLI a, LLI b, int l){return a+b*l;}; HLDecomposition hld(tree); RangeRangeSegmentTree seg(N, 0, f, 0, f, g); seg.update(0,N,1); int Q; cin >> Q; LLI ans = 0; REP(i,Q){ int A,B; cin >> A >> B; --A, --B; auto h = [&](int x, int y){ ans += seg.query(x,y+1); seg.update(x,y+1,1); }; hld.path_query_vertex(A, B, h); } cout << ans << endl; } return 0; }