各种数据都能过，但各种数据都有错死亡笔记

#include<bits/stdc++.h>
#define N 1010
#define mod 1000000007
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define Down(i,a,b) for(register int i=a;i>=b;i--)
#define Edge(i,x) for(register int i=head[x],to=e[i].t;i;i=e[i].nx,to=e[i].t)
using namespace std;
int n,k,l[N],r[N],head[N],num,f[2][N],g[2][N],v[2][N],nl,nr,mx,mn,val[200],maxn,cnt;
int now[N],plan[N],fr,to,pref[N],suf[N],frac[N],invfrac[N],st,en,nlen,ans1,ans2,pos[N];
struct E{int nx,t;}e[N];
inline void add(int f,int t){e[++num]=(E){head[f],t};head[f]=num;}
inline int fpow(int a,int b)//快速幂
{
    int res=1;
    while(b) {if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod,b>>=1;}
    return res;
}

inline void DP(int x,int fa)//DP,暴力能过应该没锅
{
    f[0][x]=1;
    int nl=max(l[x],mn),nr=min(r[x],mx);
    if(nl > nr) now[x]=plan[x]=0;
    else now[x]=nr-nl+1,plan[x]=(1ll*(nl+nr)*now[x]>>1)%mod;
    Edge(i,x)
    {
        if(to == fa) continue;
        DP(to,x);
        (f[1][x]+=1ll*f[0][x]*f[0][to]%mod)%=mod;
        (g[1][x]+=(1ll*f[0][x]*g[0][to]%mod+1ll*g[0][x]*f[0][to]%mod)%mod)%=mod;
        (f[0][x]+=f[0][to])%=mod,(g[0][x]+=g[0][to])%=mod;
    }
    (g[0][x]=(1ll*g[0][x]*now[x]%mod+1ll*plan[x]*f[0][x]%mod)%mod)%=mod;
    (g[1][x]=(1ll*g[1][x]*now[x]%mod+1ll*plan[x]*f[1][x]%mod)%mod)%=mod;
    f[0][x]=1ll*f[0][x]*now[x]%mod,f[1][x]=1ll*f[1][x]*now[x]%mod;
    return;
}

inline int lagrange(int t,int deg,int x)//插值,deg为最高次数
{
    int res=0;
    pref[0]=suf[deg+2]=suf[0]=1;
    For(i,1,deg+1) pref[i]=1ll*pref[i-1]*(x-i)%mod;//前缀(x-i)
    Down(i,deg+1,1) suf[i]=1ll*suf[i+1]*(x-i)%mod;//后缀
    For(i,1,deg+1)
    {
        int numer=1ll*v[t][i]*pref[i-1]%mod*suf[i+1]%mod;
        int deno=1ll*invfrac[i-1]*invfrac[deg+1-i]%mod*((deg+1-i)&1?mod-1:1)%mod;
        (res+=1ll*numer*deno%mod)%=mod;
    }
    return res;
}

int main()
{//f0:链的方案.g0链的和.f1:路径的方案.g1路径的和;
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    scanf("%d%d",&n,&k),frac[0]=invfrac[0]=1;
    For(i,1,n)
	{
	    scanf("%d%d",l+i,r+i);//根据分段关系将左端点排序
		pos[++cnt]=l[i],pos[++cnt]=r[i],maxn=max(maxn,r[i]+1);//为了能取完所有值维护maxr+1
		pos[++cnt]=max(l[i]-k,1),pos[++cnt]=max(r[i]-k,1);
	}
    For(i,1,n-1) scanf("%d%d",&fr,&to),add(fr,to),add(to,fr);
	pos[0]=maxn,sort(pos,pos+cnt),cnt=unique(pos,pos+cnt)-pos-1;
    For(i,1,n+3) frac[i]=1ll*frac[i-1]*i%mod;//阶乘及其逆元
    invfrac[n+3]=fpow(frac[n+3],mod-2);
    Down(i,n+2,1) invfrac[i]=1ll*invfrac[i+1]*(i+1)%mod;
    For(s,0,cnt-1)
    {
	    st=pos[s],en=pos[s+1]-1,nlen=en-st+1;//当前的连续区间
        if(nlen <= n+3)//暴力
            For(i,1,nlen)
            {
                For(j,1,n) f[0][j]=f[1][j]=g[0][j]=g[1][j]=0;
                mn=st+i-1,mx=st+i-1+k,DP(1,0);
                For(j,1,n)
                {
                    (ans1+=(now[j]+f[1][j])%mod)%=mod;
                    (ans2+=(plan[j]+g[1][j])%mod)%=mod;
                }
                For(j,1,n) f[0][j]=f[1][j]=g[0][j]=g[1][j]=0;
                mn=st+i,mx=st+i-1+k,DP(1,0);//容斥
                For(j,1,n)
                {
                    ans1=(0ll+ans1+mod+mod-now[j]-f[1][j])%mod;
                    ans2=(0ll+ans2+mod+mod-plan[j]-g[1][j])%mod;
                }
            }
        else
        {
		    v[0][0]=ans1,v[1][0]=ans2;//相当于带上一个常数
            For(i,1,n+3)//处理出n+3个前缀和
            {
                v[0][i]=v[0][i-1],v[1][i]=v[1][i-1];
                For(j,1,n) f[0][j]=f[1][j]=g[0][j]=g[1][j]=0;
                mn=st+i-1,mx=st+i-1+k,DP(1,0);
                For(j,1,n)
                {
                    (v[0][i]+=(now[j]+f[1][j])%mod)%=mod;
                    (v[1][i]+=(plan[j]+g[1][j])%mod)%=mod;
                }
                For(j,1,n) f[0][j]=f[1][j]=g[0][j]=g[1][j]=0;
                mn=st+i,mx=st+i-1+k,DP(1,0);
                For(j,1,n)
                {
                    v[0][i]=(0ll+v[0][i]+mod+mod-now[j]-f[1][j])%mod;
                    v[1][i]=(0ll+v[1][i]+mod+mod-plan[j]-g[1][j])%mod;
                }
            }//直接将所需前缀和插值求出
            ans1=lagrange(0,n+1,nlen),ans2=lagrange(1,n+2,nlen);
        }
    }
    printf("%d\n%d\n",ans1,ans2);
    return 0;
}