#include using namespace std; typedef long long ll; //#define P pair #define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I) #define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I) #define TO(x,t,f) ((x)?(t):(f)) #define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9 #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v x is sorted #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v x is sorted #define NUM(x,v) (POSU(x,v)-POSL(x,v)) //x is sorted #define REV(x) (reverse(x.begin(),x.end())) //reverse ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);} ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*b);} #define NEXTP(x) next_permutation(x.begin(),x.end()) const ll INF=ll(1e16)+ll(7); const ll MOD=1000000007LL; #define out(a) cout< HLvector; // 頂点の列 vector root_union; // root_union[i] = HLした後 頂点 HLvector[i] の根の頂点番号 vector par; // par[i]=頂点iの親 HL分解する前のグラフで1つ根に向かったやつ vector index; // index[i]=j <=> HLvector[j]=i vector depth; //depth[i]=頂点iの元の木での深さ void make_HLvector(const vector &u,const vector &v){ HLvector.clear(); root_union.clear(); int N = u.size() + 1; par.resize(N); for(int i=0;i num(N,1); vector> G(N); for(auto e:ltof) num[e.first] += num[e.second]; for(auto e:ltof) par[e.second] = e.first; for(int i=0;i > st; st.push({0,0}); // 頂点,最も浅い頂点 while(st.size()){ int i = st.top().first; int p = st.top().second; st.pop(); HLvector.push_back(i); root_union.push_back(p); int val = 0 , big_child = 0; for(auto v:G[i]){ if(num[v] > num[i]) continue; // 親には戻らない if(num[v] > val){ val = num[v]; big_child = v; } } if(val == 0) continue; for(auto v:G[i]){ if(num[v] > num[i] || v == big_child) continue; st.push({v,v}); } st.push({big_child,p}); } index.resize(N); for(int i=0;i > index_route(int u,int v){ // u,vパスを連結成分で区切った時のパスの(HLvectorの)indexを示す vector< pair > res; while(root_union[index[u]] != root_union[index[v]]){ if(depth[ root_union[index[u]] ] < depth[ root_union[index[v]] ]) swap(u,v); int a = root_union[ index[u] ]; //u と a のindex res.push_back({ index[a] , index[u] }); u = par[a]; assert(u>=0); } res.push_back({min(index[u],index[v]),max(index[u],index[v])}); return res; } vector< pair > leaf_to_root(const vector &u,const vector &v,const int root){ // return int yet = -1; vector d(u.size()+1,yet); vector< pair > res; queue Q; Q.push(root); d[root] = 0; vector< vector > G(u.size()+1); for(int i=0;i } }; template class Lazy_Seg_Tree{ public: // 0-index // buketは区間変更の値 datは区間の答え // initial_d,initial_b は buket dat の 単位元 T make_dat_from_buket(T da, T bu, T s){//dat[k] = make_dat_from_buket(dat[k],buket[k],r-l); return da + bu * s; } T buket_to_child(T ch, T pa){// buket[2*k+1] = buket_to_child(buket[2*k+1],buket[k]); return ch + pa; } T buket_update(T bu , T x , T s){// buket[k] = buket_update(buket[k],x,r-l); return bu + x; } T dat_update(T dc1, T dc2){// dat[k] = dat_update(dat[2*k+1],dat[2*k+2]); return (dc1 + dc2); } vector dat,buket; T initial_d,initial_b,M; int n; Lazy_Seg_Tree(int n0_=1,T initial_dat=1,T initial_buket=0 ,T M_=1){ initsize(n0_,initial_dat,initial_buket,M_); } void initsize(int n0,T initial_da,T initial_bu,T M_){ M = M_; initial_d = initial_da; initial_b = initial_bu; int k=1; while(k1){ buket[2*k+1] = buket_to_child(buket[2*k+1],buket[k]); buket[2*k+2] = buket_to_child(buket[2*k+2],buket[k]); } buket[k] = initial_b; } } void operate(int a,int b, T x, int k=0,int l=0, int r=-1){ if(r<0)r=n; eval(k,l,r); if(b<=l || r<=a)return; if(a<=l && r<=b){ buket[k] = buket_update(buket[k],x,r-l); eval(k,l,r); }else{ operate(a,b,x,2*k+1,l,(l+r)/2); operate(a,b,x,2*k+2,(l+r)/2,r); dat[k] = dat_update(dat[2*k+1],dat[2*k+2]); } } T get(int a,int b,int k=0,int l=0,int r=-1){ if(r<0)r=n; if(b<=l || r<=a) return initial_d; eval(k,l,r); if(a<=l && r<=b) return dat[k]; T vl = get(a,b,2*k+1,l,(l+r)/2); T vr = get(a,b,2*k+2,(l+r)/2,r); return dat_update(vl,vr); } }; int main(){ int N; cin >> N; vector u(N-1),v(N-1); FOR(i,0,N-1){ cin >> u[i] >> v[i]; u[i]--; v[i]--; } HL hl; hl.make_HLvector(u,v); Lazy_Seg_Tree sg(N,0,0,MOD); int Q; cin >> Q; ll ans = 0; while(Q--){ int a,b; cin >> a >> b; a--; b--; auto r = hl.index_route(a,b); for(auto e:r){ a = e.first; b = e.second; sg.operate(a,b+1,1,0,0,-1); } for(auto e:r){ ans += sg.get(e.first,e.second+1,0,0,-1); /*for(int i=e.first;i<=e.second;i++){ ans += sg.get(i,i+1,0,0,-1); }*/ //cout << "["<