rt，用的是点分治套平衡树，只有最后一个点 WA 了，这是代码：

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=4e5;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int n,m,K,maxd,tot,pos[Maxn+5],vis[Maxn+5];
int rt,sum,siz[Maxn+5],maxs[Maxn+5];
ll ans[Maxn+5][2],len[Maxn+5],all[Maxn+5],hzh[Maxn+5];
int Max[Maxn+5],Min[Maxn+5],dep[Maxn+5];
struct Query{int l,r;} q[Maxn+5];
vector<int> v[Maxn+5],w[Maxn+5];

struct Node{int l,r,p,q,key,siz;} t[Maxn*40+5];
#define ls(x) t[x].l
#define rs(x) t[x].r
struct Treap
{
    int rt;
    inline int NewNode(int p,int q)
    {
        t[++tot]=(Node){0,0,p,q,rand(),1};
        return tot;
    }
    inline void push_up(int x) {t[x].siz=t[ls(x)].siz+t[rs(x)].siz+1;}
    inline void Splitp(int now,int val,int &x,int &y)
    {
        if(!now) {x=y=0; return;}
        if(t[now].p<=val) x=now,Splitp(rs(now),val,rs(now),y);
        else y=now,Splitp(ls(now),val,x,ls(now));
        push_up(now);
    }
    inline void Splitq(int now,int val,int &x,int &y)
    {
        if(!now) {x=y=0; return;}
        if(t[now].q<=val) x=now,Splitq(rs(now),val,rs(now),y);
        else y=now,Splitq(ls(now),val,x,ls(now));
        push_up(now);
    }
    inline int Merge(int x,int y)
    {
        if(!x || !y) return x+y;
        if(t[x].key<=t[y].key) {rs(x)=Merge(rs(x),y),push_up(x); return x;}
        else {ls(y)=Merge(x,ls(y)),push_up(y); return y;}
    }
    inline void Insert(int p,int q)
    {
        int x=NewNode(p,q),a,b; Splitp(rt,p,a,b);
        rt=Merge(a,Merge(x,b));
    }
    inline int Prep(int val)
    {
        int a,b,res; Splitp(rt,val-1,a,b),res=a;
        while(rs(res)) res=rs(res);
        rt=Merge(a,b); return res;
    }
    inline int Preq(int val)
    {
        int a,b,res; Splitq(rt,val-1,a,b),res=a;
        while(rs(res)) res=rs(res);
        rt=Merge(a,b); return res;
    }
    inline int Nxtp(int val)
    {
        int a,b,res; Splitp(rt,val,a,b),res=b;
        while(ls(res)) res=ls(res);
        rt=Merge(a,b); return res;
    }
    inline int Nxtq(int val)
    {
        int a,b,res; Splitq(rt,val,a,b),res=b;
        while(ls(res)) res=ls(res);
        rt=Merge(a,b); return res;
    }
    inline void Add(int p,int q)
    {
        int res=Prep(p+1); if(res && t[res].q>=q) return;
        int a,b,c; Splitp(rt,p-1,a,b),Splitq(b,q,b,c);
        rt=Merge(a,c); Insert(p,q);
    }
    inline void Count(int p,int q)
    {
        int a=Nxtp(p-1),b=Preq(q);
        int c=Prep(p),d=Nxtq(q-1);
        if(a)
        {
            int l=min(p,t[a].p),r=max(q,t[a].q);
            if(l<r) pos[l]=min(pos[l],r-1);
        }
        if(b)
        {
            int l=min(p,t[b].p),r=max(q,t[b].q);
            if(l<r) pos[l]=min(pos[l],r-1);
        }
        if(c)
        {
            int l=min(p,t[c].p),r=max(q,t[c].q);
            if(l<r) pos[l]=min(pos[l],r-1);
        }
        if(d)
        {
            int l=min(p,t[d].p),r=max(q,t[d].q);
            if(l<r) pos[l]=min(pos[l],r-1);
        }
    }
} T[Maxn+5];

inline void GetRt(int x,int f)
{
    siz[x]=1,maxs[x]=0;
    for(auto y:v[x]) if(y!=f && !vis[y])
        GetRt(y,x),siz[x]+=siz[y],maxs[x]=max(maxs[x],siz[y]);
    maxs[x]=max(maxs[x],sum-siz[x]);
    rt=(maxs[x]<maxs[rt]?x:rt);
}
inline void dfs1(int x,int f)
{
    dep[x]=dep[f]+1,maxd=max(maxd,dep[x]);
    if(dep[x]<=K+1) T[K+1-dep[x]].Count(Min[x],Max[x]);
    for(auto y:v[x]) if(y!=f && !vis[y])
    {
        Min[y]=min(Min[x],y),Max[y]=max(Max[x],y);
        dfs1(y,x);
    }
}
inline void dfs2(int x,int f)
{
    if(dep[x]<=K+1) T[dep[x]].Add(Min[x],Max[x]);
    for(auto y:v[x]) if(y!=f && !vis[y]) dfs2(y,x);
}
inline void Solve(int x)
{
    T[0].Insert(x,x),dep[x]=maxd=0;
    for(auto y:v[x]) if(!vis[y])
    {
        Max[y]=max(x,y),Min[y]=min(x,y);
        dfs1(y,x),dfs2(y,x);
    }
    For(i,1,tot) t[i]=(Node){0,0,0,0,0,0};
    tot=0;
    For(i,0,min(maxd,K+1)) T[i].rt=0;
}
inline void dfs(int x)
{
    vis[x]=1; Solve(x);
    for(auto y:v[x]) if(!vis[y])
        rt=0,sum=siz[y],GetRt(y,0),GetRt(rt,0),dfs(rt);
}

int main()
{
    srand(time(0));
    n=read(),m=read(),K=read(),maxs[0]=n+5;
    For(i,1,n) pos[i]=n;
    For(i,1,n-1)
    {
        int a=read(),b=read();
        v[a].push_back(b),v[b].push_back(a);
    }
    rt=0,sum=n,GetRt(1,0),GetRt(rt,0),dfs(rt);
    Rof(i,n-1,1) pos[i]=min(pos[i],pos[i+1]);
    For(i,1,n)
    {
        len[i]=pos[i]-i+1;
        all[i]=len[i]*(len[i]+1)/2ll;
    }
    For(i,1,n) len[i]+=len[i-1],all[i]+=all[i-1];
    For(i,1,n) hzh[i]=hzh[i-1]+1ll*i*(i+1)/2ll;
    For(i,1,m)
    {
        q[i].l=read(),q[i].r=read();
        w[q[i].r].push_back(i);
    }
    int it=0;
    For(i,1,n)
    {
        while(it<n && pos[it+1]<=i) it++;
        for(auto j:w[i])
        {
            int l=q[j].l,r=q[j].r;
            if(l<=it)
            {
                ans[j][0]+=(len[it]-len[l-1]);
                ans[j][1]+=(all[it]-all[l-1]);
            }
            if(it<r)
            {
                int id=max(it,l-1);
                ans[j][0]+=1ll*(r-id)*(r-id+1)/2ll;
                ans[j][1]+=hzh[r-id];
            } 
        }
    }
    For(i,1,m) printf("%lld %lld\n",ans[i][0],ans[i][1]);
    return 0;
}