#include using namespace std; #define endl '\n' #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define spa << " " << #define lfs <= (ll)(m); i--) using ll = long long; using ld = long double; const ll MOD = 1e9+7; //const ll MOD = 998244353; const ll INF = 1e18; using P = pair; template void chmin(T &a,T b){if(a>b)a=b;} template void chmax(T &a,T b){if(a void ans(bool x,T1 y,T2 z){if(x)cout< void debug(vector>v,ll h,ll w){for(ll i=0;iv,ll h,ll w){for(ll i=0;i void debug(vectorv,ll n){if(n!=0)cout< vector>vec(ll x, ll y, T w){ vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} template vectordx={1,0,-1,0,1,1,-1,-1}; vectordy={0,1,0,-1,1,-1,1,-1}; template vector make_v(size_t a,T b){return vector(a,b);} template auto make_v(size_t a,Ts... ts){ return vector(a,make_v(ts...)); } template struct LazySegmentTree{ using F = function; vector data, lazy; ll n,lastlen = 1; F func = [](T a, T b){return a+b;}; T iden = 0; //identity element F f_lazy = [](T a, T b){return a+b;}; T iden_l = 0; F f_trans = [](T a, ll range){return a*(ll)range;}; LazySegmentTree(vector v){ n = (ll)v.size(); while(lastlen < n)lastlen *= 2; data.assign(lastlen*2-1,iden); lazy.assign(lastlen*2-1,iden_l); for(ll i=0;i=0;i--){ data[i] = func(data[2*i+1], data[2*i+2]); } } void eval(ll k, ll left, ll right){ if(lazy[k] != iden_l){ data[k] = f_lazy(data[k], f_trans(lazy[k],right-left)); if(k <= lastlen - 2){ lazy[2*k+1] = f_lazy(lazy[2*k+1],lazy[k]); lazy[2*k+2] = f_lazy(lazy[2*k+2],lazy[k]); } lazy[k] = iden_l; } } void update(ll a,ll b,T x,ll point=0LL, ll left=0LL,ll right=-1LL){ if(right<0)right=lastlen; eval(point,left,right); if(b <= left || right <= a); else if(a <= left && right <= b ){ lazy[point] = x; eval(point,left,right); } else{ update(a,b,x,point*2+1, left, (left+right)/2); update(a,b,x,point*2+2, (left+right)/2, right); data[point] = func(data[2*point+1], data[2*point+2]); } } T query(ll a,ll b,ll point=0LL,ll left=0LL,ll right=-1LL){ if(right<0)right=lastlen; T ret = iden; eval(point,left,right); if(b <= left || right <= a); else if(a <= left && right <= b ){ ret = func(ret,data[point]); } else{ T p=query(a,b,point*2+1, left, (left+right)/2); T q=query(a,b,point*2+2, (left+right)/2, right); data[point] = func(data[2*point+1], data[2*point+2]); ret = func(ret,p); ret = func(ret,q); } return ret; } void print(){ ll num=0; for(ll i=lastlen;i>0;i/=2)num++; ll tmp=1; for(ll i=0;isz;//部分木サイズ vectordepth,par,hv_chi; vectorhead; vector>g;//隣接リスト vectoredges;//データ構造に乗せるedge列 vectoridx;//edge列のindexを下側の頂点から求める HLD(vector>G,ll r) :g(G),n(G.size()),root(r){ depth.assign(n,-1),par.assign(n,-1),hv_chi.assign(n,-1); sz.assign(n,-1),head.assign(n,-1),idx.assign(n,-1); edges.emplace_back(0,0); idx[root] = 0; dfs_sz(root,0); dfs_hl(root); } ll dfs_sz(ll k, ll d){ depth[k] = d; ll sum_sz = 0; ll max_sz = 0,idx = -1; for(ll i=0;i depth[head[q]])swap(p,q); if(head[p] == head[q])break; q = par[head[q]]; } if(depth[p] > depth[q])swap(p,q); return p; } vector>query_edge(ll p,ll q){ vectorv = {p,q}; ll r=lca(p,q); vector>ret; for(ll i=0;i<2;i++){ while(1){ if(v[i]==r)break; if(head[v[i]]==head[r]){ ret.emplace_back(idx[r]+1,idx[v[i]]+1); break; } ret.emplace_back(idx[head[v[i]]],idx[v[i]]+1); v[i] = par[head[v[i]]]; } } return ret; } vector>query_vertex(ll p,ll q){ vectorv = {p,q}; ll r=lca(p,q); vector>ret; for(ll i=0;i<2;i++){ while(1){ if(head[v[i]]==head[r]){ ret.emplace_back(idx[r]+i,idx[v[i]]+1); break; } ret.emplace_back(idx[head[v[i]]],idx[v[i]]+1); v[i] = par[head[v[i]]]; } } return ret; } }; int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); ll n;cin>>n; vector>g(n); rep(i,0,n-1){ ll u,v;cin>>u>>v; g[u-1].EB(v-1,1); g[v-1].EB(u-1,1); } HLD hld(g,0); LazySegmentTreesegtree(vector(n,0)); ll q;cin>>q; ll ret=0; rep(i,0,q){ ll a,b;cin>>a>>b; auto p=hld.query_vertex(a-1,b-1); rep(j,0,p.size()){ segtree.update(p[j].fi,p[j].se,1); ret+=segtree.query(p[j].fi,p[j].se); } } cout<