#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) int n,q,fa[200300],siz[200300],hs[200300],tk; vector<int>g[200300]; struct ask{int l,r,id,s;};vector<ask>A[200030]; struct modi{int l,r,k;};vector<modi>M[200300]; int ANS[200300]; struct node{ int a,b; friend node operator +(const node A,const node B){return (node){A.a+B.a,A.b+B.b};} friend node operator *(int b,const node A){return (node){A.a*b,A.b*b};} inline int f(int x){return a*x+b;} }w[200300<<2],tg[200300<<2]; #define lc(x) (x<<1) #define rc(x) (x<<1|1) inline void upd(int x){w[x]=w[lc(x)]+w[rc(x)];} inline void pd(int x,int l,int r){ int mid=l+r>>1,L=mid-l+1,R=r-mid; w[lc(x)]=w[lc(x)]+L*tg[x],w[rc(x)]=w[rc(x)]+R*tg[x]; tg[lc(x)]=tg[lc(x)]+tg[x],tg[rc(x)]=tg[rc(x)]+tg[x]; tg[x]=(node){0,0}; } inline void bd(int x,int l,int r){ if(l==r){w[x]={n,0};return ;} int mid=l+r>>1; bd(lc(x),l,mid),bd(rc(x),mid+1,r),upd(x); } inline void mod(int x,int l,int r,int L,int R,node p){ if(L<=l&&r<=R){tg[x]=tg[x]+p,w[x]=w[x]+(r-l+1)*p;return ;} pd(x,l,r); int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,p); if(R>mid)mod(rc(x),mid+1,r,L,R,p); upd(x); } inline node gt(int x,int l,int r,int L,int R){ if(L<=l&&r<=R)return w[x]; pd(x,l,r); int mid=l+r>>1; node res={0,0}; if(L<=mid)res=res+gt(lc(x),l,mid,L,R); if(R>mid)res=res+gt(rc(x),mid+1,r,L,R); return res; } inline void sub(int l,int r,int k){if(!k)return ; M[l].push_back({l,r,k}),M[r+1].push_back({l,r,-k}); } struct ODT{ set<pair<pii,int>>S; inline void ins(int x,int tk){ int l=x,r=x; while(1){ auto it=S.upper_bound({{r,r},-1e9}); if(it==S.end()||p1(p1(*it))!=r+1)break; r=p2(p1(*it)); sub(p1(p1(*it)),p2(p1(*it)),tk-p2(*it)),S.erase(it); } while(1){ auto it=S.upper_bound({{l,l},-1e9}); if(it==S.begin())break; it--; if(p2(p1(*(it)))!=l-1)break; l=p1(p1(*it)); sub(p1(p1(*it)),p2(p1(*it)),tk-p2(*it)),S.erase(it); } S.insert({{l,r},tk}); } inline void del(int x,int tk){ auto it=S.upper_bound({{x,1e9},1e9}); it--; int l=p1(p1(*it)),r=p2(p1(*it)); sub(l,r,tk-p2(*it)); S.erase(it); if(l!=x)S.insert({{l,x-1},tk}); if(r!=x)S.insert({{x+1,r},tk}); } inline void clr(int tk){for(auto it:S)sub(p1(p1(it)),p2(p1(it)),tk-p2(it));S.clear();} }OT[2]; inline void init(){OT[0].clr(tk),OT[1].clr(tk),tk=0,OT[0].S.insert({{1,n},tk});} inline void dfs(int u){siz[u]=1; for(int v:g[u])if(v!=fa[u]){ fa[v]=u; dfs(v); siz[u]+=siz[v]; if(siz[v]>siz[hs[u]])hs[u]=v; } } inline void ins(int u){OT[0].del(u,tk),OT[1].ins(u,tk);} inline void INS(int u){ins(u);for(int v:g[u])if(v!=fa[u])INS(v);} inline void calc(int u){ for(int v:g[u])if(v!=fa[u]&&v!=hs[u])calc(v); if(hs[u])calc(hs[u]); for(int v:g[u])if(v!=fa[u]&&v!=hs[u])INS(v); ins(u),tk++; if(hs[fa[u]]!=u)init(); } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } init(),dfs(1),calc(1); cin>>q; for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; A[l-1].push_back({l,r,i,-1}); A[r].push_back({l,r,i,1}); } bd(1,1,n); for(int i=1;i<=n;i++){ for(auto m:M[i])mod(1,1,n,m.l,m.r,{-m.k,m.k*(i-1)}); for(auto a:A[i])ANS[a.id]+=a.s*gt(1,1,n,a.l,a.r).f(i); } for(int i=1;i<=q;i++)cout<<ANS[i]/2<<"\n"; cout.flush(); return 0; }