#include #include using namespace std; using namespace atcoder; typedef long long int ll; typedef unsigned long long ull; typedef long double ld; typedef pair pll; typedef vector vll; typedef vector vvll; typedef vector vvvll; typedef vector vvvvll; typedef vector vvvvvll; typedef vector vpll; typedef vector vvpll; typedef vector vb; typedef vector vvb; typedef vector vd; typedef vector vvd; typedef vector vs; typedef vector vvs; typedef vector vc; typedef vector vvc; using Graph1 = vector>; #define rep(i,n) for(ll i=0;i=0;i--) #define pper(i,a,n) for(ll i=n-1;i>=a;i--) #define fs first #define sc second #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() const ll INF = 1LL<<60; const int mod1 = 1000000007; const int mod2 = 998244353; //最大更新、最小更新 templatebool chmax(T& x,T y){if(xbool chmin(T & x,T y){if(x>y){x = y;return true;}else return false;} template using pq = priority_queue; template using pqg = priority_queue,greater>; using mint = modint998244353; class HLD{ private: int V; vvll g; vll stsize,parent,pathtop,in,out; int root; void BuildStsize(int u,int p){ stsize[u] = 1;parent[u] = p; for(ll &v:g[u]){ if(v==p){ if(v==g[u].back()) break; else swap(v,g[u].back()); } BuildStsize(v,u); stsize[u]+=stsize[v]; if(stsize[v]>stsize[g[u][0]]){ swap(v,g[u][0]); } } } void BuildPath(int u, int p, int& tm){ in[u] = tm++; for(ll v:g[u]){ if(v == p) continue; pathtop[v] = (v == g[u][0] ? pathtop[u] : v); BuildPath(v, u, tm); } out[u] = tm; } public: void add_edge(int u,int v){ g[u].push_back(v),g[v].push_back(u); } void build(int _root){ root = _root; int tm = 0; BuildStsize(root,-1); pathtop[root] = root; BuildPath(root,-1,tm); } inline int get(int a){ return in[a]; } int lca(int a,int b){ int pa = pathtop[a],pb=pathtop[b]; while(pathtop[a]!=pathtop[b]){ if(in[pa]>in[pb]){ a = parent[pa],pa = pathtop[a]; } else{ b=parent[pb],pb=pathtop[b]; } } if(in[a]>in[b])swap(a,b); return a; } void subtree_query(int a,const function &func){ func(in[a],out[a]); } void path_query(int a,int b,const function &func){ int pa = pathtop[a],pb=pathtop[b]; while(pathtop[a]!=pathtop[b]){ if(in[pa]>in[pb]){ func(in[pa],in[a]); a=parent[pa],pa=pathtop[a]; } else{ func(in[pb],in[b]); b=parent[pb],pb=pathtop[b]; } } if(in[a]>in[b]) swap(a,b); func(in[a],in[b]); } HLD(int node) :V(node),g(V),stsize(V,0),parent(V,-1),pathtop(V,-1),in(V,-1),out(V,-1){} }; template class segtre { private: int n,sz,h; vector node, lazy_update, lazy_add; vector lazyFlag; public: segtre(vector v) : n(1), sz((int)v.size()), h(0){ while(n < sz) n *= 2, h++; node.resize(2*n, 0); lazy_update.resize(2*n, 0); lazyFlag.resize(2*n, false); lazy_add.resize(2*n, 0); for(int i = 0; i < sz; i++) node[i+n] = v[i]; for(int i=n-1; i>=1; i--) node[i] = node[2*i] + node[2*i+1]; } void eval(int k) { if(lazyFlag[k]){ lazy_update[k] += lazy_add[k]; node[k] = lazy_update[k]; if(k < n) { lazy_add[2*k] = lazy_add[2*k+1] = 0; lazy_update[2*k] = lazy_update[2*k+1] = lazy_update[k] / 2; lazyFlag[2*k] = lazyFlag[2*k+1] = true; } lazy_add[k] = 0, lazyFlag[k] = false; }else if(lazy_add[k] != 0){ node[k] += lazy_add[k]; if(k < n){ lazy_add[2*k] += lazy_add[k] / 2; lazy_add[2*k+1] += lazy_add[k] / 2; } lazy_add[k] = 0; } } void update(int a, int b, T x, int k=1, int l=0, int r=-1) { if(r < 0) r = n; eval(k); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy_add[k] = 0; lazy_update[k] = x*(r-l); lazyFlag[k] = true; eval(k); }else{ update(a, b, x, 2*k, l, (l+r)/2); update(a, b, x, 2*k+1, (l+r)/2, r); node[k] = node[2*k] + node[2*k+1]; } } void add(int a, int b, T x, int k=1, int l=0, int r=-1){ if(r < 0) r = n; eval(k); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy_add[k] += x*(r-l); eval(k); }else{ add(a, b, x, 2*k, l, (l+r)/2); add(a, b, x, 2*k+1, (l+r)/2, r); node[k] = node[2*k] + node[2*k+1]; } } T query(int a, int b) { a += n, b += n - 1; for(int i = h; i > 0; i--) eval(a >> i), eval(b >> i); b++; T res1 = 0, res2 = 0; while(a < b) { if(a & 1) eval(a), res1 += node[a++]; if(b & 1) eval(--b), res2 += node[b]; a >>= 1, b >>= 1; } return res1 + res2; } void print(){for(int i = 0; i < sz; i++)cout<> n; HLD hl(n); vvll gr(n); rep(i,n-1){ int u,v;cin >> u >>v; --u,--v; hl.add_edge(u,v); } hl.build(0); segtre seg(vll(n,0)); int q;cin >>q; ll sum = 0; rep(i,q){ int u,v;cin >> u >> v; hl.path_query(u-1,v-1,[&](int k,int l){ seg.add(k,l+1,1); sum += seg.query(k,l+1); }); } cout << sum<