#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) #define pb push_back #define inx(u) int I=h[u],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v #define pii pair<int,int> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c==EOF)return -1;if(c=='-')f=-1;c=getchar();}x=c-'0';c=getchar();while(c<='9'&&c>='0'){x*=10;x+=c-'0';c=getchar();}return x*f;} const int MAXN=100010,N=60,inf=1000000000,Mod=1011451423,Mod2=998244853,base=131,base2=2333; struct Edge{int v,nx;}edge[MAXN<<1];int h[MAXN],CNT=1;void add_side(int u,int v){edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,siz[MAXN],son[MAXN],dep[MAXN],tot; struct node{ int l,r,x,t; bool operator<(const node&G)const{ return x<G.x; } }a[MAXN*N]; void dfs(int u,int lst){ int mx=0;siz[u]=1; for(inx(u))if(v!=lst){ dep[v]=dep[u]+1; dfs(v,u); siz[u]+=siz[v]; if(siz[v]>mx){ mx=siz[v]; son[u]=v; } } } void inset(int l,int r,int x){if(!x)return; // cout<<l<<" "<<r<<" "<<x<<endl; a[++tot]={l,r,l,-x},a[++tot]={l,r,r+1,x}; } struct ODT{ set<pair<pii,int> >st; void inst(int l,int r,int t){ st.insert(mk(mk(l,r),t)); } void add(int x,int t){ pair<pii,int>rt={{x,x},t}; auto it=st.upper_bound(mk(mk(x,x),-1e9)); if(!st.empty()&&it!=st.end()&&(*it).fr.fr==x+1){ pair<pii,int> tmp=*it; inset(tmp.fr.fr,tmp.fr.sc,t-tmp.sc); rt.fr.sc=tmp.fr.sc; st.erase(tmp); } it=st.upper_bound(mk(mk(x,x),-1e9)); if(!st.empty()&&it!=st.begin()){ it--; if((*it).fr.sc==x-1){ pair<pii,int> tmp=*it; rt.fr.fr=tmp.fr.fr; inset(tmp.fr.fr,tmp.fr.sc,t-tmp.sc); st.erase(tmp); } } st.insert(rt); } void del(int x,int t){ auto it=st.upper_bound(mk(mk(x,1e9),1e9));it--; pair<pii,int>tmp=*it; inset(tmp.fr.fr,tmp.fr.sc,t-tmp.sc);st.erase(tmp); if(tmp.fr.sc>x)st.insert(mk(mk(x+1,tmp.fr.sc),t));//,cout<<"sto"<<x+1<<" "<<tmp.fr.sc<<endl; if(tmp.fr.fr<x)st.insert(mk(mk(tmp.fr.fr,x-1),t));//,cout<<"sto"<<tmp.fr.fr<<" "<<x-1<<endl; } void clear(int t){ for(auto o:st){inset(o.fr.fr,o.fr.sc,t-o.sc);} st.clear(); } }T[2]; int tim; void init(){T[1].clear(tim),T[0].clear(tim),tim=0,T[0].inst(1,n,tim);} void ins(int x){T[1].add(x,tim);T[0].del(x,tim);} void dfs1(int u,int lst){ ins(u); for(inx(u))if(v!=lst){ dfs1(v,u); } } int ans[MAXN]; void dfs2(int u,int lst){ for(inx(u))if(v!=son[u]&&v!=lst){ dfs2(v,u); } if(son[u])dfs2(son[u],u); for(inx(u))if(v!=son[u]&&v!=lst){ dfs1(v,u); } ins(u),tim++; if(u!=son[lst])init(); } pii mg(pii x,pii y){return mk(x.fr+y.fr,x.sc+y.sc);} struct segtree{ pii t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos]=mg(t[lson],t[rson]); } void pushdown(int pos,int l,int r){ if(lz[pos].fr){ int mid=(l+r)>>1; pii x=lz[pos]; t[lson].fr+=x.fr*(mid-l+1); t[lson].sc+=x.sc*(mid-l+1); lz[lson].fr+=x.fr; lz[lson].sc+=x.sc; t[rson].fr+=x.fr*(r-mid); t[rson].sc+=x.sc*(r-mid); lz[rson].fr+=x.fr; lz[rson].sc+=x.sc; lz[pos].fr=lz[pos].sc=0; } } void build(int pos,int l,int r){ if(l==r){t[pos]={n,0};return;} int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int ql,int qr,pii x){ if(ql<=l&&qr>=r){ t[pos].fr+=x.fr*(r-l+1); t[pos].sc+=x.sc*(r-l+1); lz[pos].fr+=x.fr; lz[pos].sc+=x.sc; return; } pushdown(pos,l,r); int mid=(l+r)>>1; if(ql<=mid)update(lson,l,mid,ql,qr,x); if(qr>mid)update(rson,mid+1,r,ql,qr,x); pushup(pos); } pii query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r){ return t[pos]; } pushdown(pos,l,r); int mid=(l+r)>>1;pii res={0,0}; if(ql<=mid)res=query(lson,l,mid,ql,qr); if(qr>mid)res=mg(res,query(rson,mid+1,r,ql,qr)); return res; } }TR; struct question{ int l,r,x,id,ty; bool operator<(const question&G)const{ return x<G.x; } }q[MAXN<<1]; int as[MAXN]; void slv(){ n=read(); for(int i=2;i<=n;i++){ int u=read(),v=read(); add_side(u,v); } init(); dfs(1,1); dfs2(1,1); // return; m=read(); for(int i=1;i<=m;i++){ int l=read(),r=read(); q[i]={l,r,l-1,i,-1}; q[i+m]={l,r,r,i,1}; } sort(q+1,q+2*m+1); sort(a+1,a+tot+1); // for(int i=1;i<=tot;i++)cout<<a[i].l<<" "<<a[i].r<<" "<<a[i].x<<" "<<a[i].t<<endl; TR.build(1,1,n); for(int i=1,j=1;i<=2*m;i++){ while(j<=tot&&a[j].x<=q[i].x)TR.update(1,1,n,a[j].l,a[j].r,mk(a[j].t,-(a[j].x-1)*a[j].t)),j++; pii tmp=TR.query(1,1,n,q[i].l,q[i].r); as[q[i].id]+=q[i].ty*(tmp.fr*q[i].x+tmp.sc); } for(int i=1;i<=m;i++){ printf("%lld\n",as[i]/2); } } signed main(){ slv(); return 0; }