#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;
}

``

#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=5010,inf=1000'000'000,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<<1];
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].l*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(){
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    slv();
    return 0;
}``