求助卡常

#include<bits/stdc++.h>

const int N = 205;
const int Mod = 1e9 + 7;
const int inv = 500000004;
typedef long long ll;
#define ep emplace_back
using namespace std;

vector<int> e[N];

ll f[N], dp[N];
ll sum[N], k[N];
int li[N], ri[N];
int n, K, V;
ll ansf, ansdp;

void dfs1(int u,int fa) {
    int child = 0;
    ll sumdp = 0, sumf = 0;
    for(auto v : e[u]){
        if(v==fa)continue;
        child++;
        dfs1(v,u);
        sumdp = (sumdp + dp[v]);
        sumf = (sumf + f[v]);
    }
    sumdp %= Mod, sumf %= Mod;
    if(!child) {f[u] = k[u]; dp[u] = sum[u]; return ;}
    dp[u] = (sum[u] * (1 + sumf) + sumdp * k[u]) % Mod;
    f[u] = k[u] * (1 + sumf) % Mod; // change (sumf) into (1 + sumf)
}

void dfs2(int u, int fa) {
    ansf = (ansf + f[u]) ;
    ansdp = (ansdp + dp[u]) ;

    for(auto v : e[u]){
        if(v==fa)continue;
        ll du = (dp[u] - sum[u] * f[v] - dp[v] * k[u] ) % Mod;
        ll fu = (f[u] - f[v] * k[u] ) % Mod;
        dp[v] = (dp[v] + sum[v] * fu + du * k[v] ) % Mod;
        f[v] = (f[v] + fu * k[v] ) % Mod;
        dfs2(v, u);
    }
}

ll Ansf, Ansdp;

void solve(int l, int r) {
    for(int i=1;i<=n;++i){
        ll L = max(li[i],l);
        ll R = min(ri[i],r);
        k[i]=max(0ll, R-L+1); 
        sum[i]=max((R+L)*(R-L+1)%Mod*inv%Mod,0ll);//I forget it;
    }
    // cerr<<l<<" "<<r<<" : ";
    // for(int i=1;i<=n;++i)cerr<<k[i]<<" "<<sum[i]<<endl;
    memset(f,0,sizeof f);
    memset(dp,0,sizeof dp);
    ansf = ansdp = 0; 
    dfs1(1, 0), dfs2(1, 0); 
    // cerr << ansf << " " << ansdp << endl;
}

int main(){
    ios::sync_with_stdio(0);

    cin >> n >> K;
    ll SigmaF = 0, SigmaDp = 0;
    for(int i=1;i<=n;++i){
        cin>>li[i]>>ri[i];
        SigmaF = (ri[i] - li[i] + 1 + SigmaF);
        SigmaDp = ((ri[i] - li[i] + 1) * (ll)(ri[i] + li[i])%Mod*inv%Mod + SigmaDp);
        V = max(V, ri[i]);
    }
    SigmaF %= Mod, SigmaDp %= Mod;
    for(int i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        e[u].ep(v), e[v].ep(u);
    }
    for(int i=1;i<=V;++i){
        int lv = i, rv = min(V, i + K);
        solve(lv, rv);
        ansf %= Mod, ansdp %= Mod;
        Ansf = (Ansf + ansf);
        Ansdp = (Ansdp + ansdp);
        if(lv == rv) continue; 
        solve(lv + 1, rv);
        ansf %= Mod, ansdp %= Mod;
        Ansf = (Ansf - ansf);
        Ansdp = (Ansdp - ansdp);
    }
    Ansf = (Ansf % Mod + Mod) % Mod;
    Ansdp = (Ansdp % Mod + Mod) % Mod;
    cout << ((Ansf + SigmaF) % Mod * inv) % Mod << "\n" << ((Ansdp + SigmaDp) % Mod * inv) % Mod << endl;
    return 0;
}