神奇 dp。发现我看到 dp 大多数时候只会暴力。那我约等于退役了啊。
题意：自己看。
首先有一个显然的暴力。枚举一个最小值 \(L\)，然后区间就限定在了 \([L,L+K]\)。那么普及组都能看出来这个 dp 可以前缀和优化。然后由于这个 dp 不能确定最小值一定取到，所以减一个 \([L+1,L+K]\) 的答案。这玩意复杂度显然 \(O(n\times 值域)\) 的。
然后考虑到每次最小值 \(+1\) ，最大值 \(+1\) 的过程。如果没有节点的 \([l_i,r_i]\) 被包含进去或者不再被包含，那么相当于让所有情况下的值 \(+1\)。如果将每个节点的可选区间表示成一次函数的形式，那么可以发现方案数就是所有节点的函数乘起来的 \(n\) 次多项式，求和就是再多一次。
而且这个段数显然是 \(O(n)\) 的。那么对于每一段前缀和拉格朗日插值一下就行了。总复杂度 \(O(n^3)\)。
然而这题有点 jb 卡常。不知道什么心态。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int mod=1000000007;
int n,K,ans1,ans2;
struct node{
int v,next;
}edge[410];
int t,head[210];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int l[210],r[210];
int f[210],g[210],sumf[210],sumg[210];
int s(int n){
return 1ll*n*(n+1)/2%mod;
}
void dfs(int x,int fa,int L,int R){
int l1=max(L,l[x]),r1=min(R,r[x]);
if(l1>r1)l1=r1+1;
int ret=r1-l1+1,tmp=(s(r1)-s(l1-1)+mod)%mod;
f[x]=sumf[x]=ret;g[x]=sumg[x]=tmp;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=fa){
dfs(edge[i].v,x,L,R);
f[x]=(f[x]+1ll*sumf[x]*sumf[edge[i].v])%mod;
g[x]=(g[x]+1ll*sumf[x]*sumg[edge[i].v]+1ll*sumf[edge[i].v]*sumg[x])%mod;
sumf[x]=(sumf[x]+1ll*sumf[edge[i].v]*ret)%mod;
sumg[x]=(sumg[x]+1ll*sumg[edge[i].v]*ret+1ll*tmp*sumf[edge[i].v])%mod;
}
}
}
void getans(int val,int L,int R){
for(int i=1;i<=n;i++)f[i]=g[i]=sumf[i]=sumg[i]=0;
dfs(1,0,L,R);
for(int i=1;i<=n;i++)ans1=(ans1+1ll*f[i]*val)%mod,ans2=(ans2+1ll*g[i]*val)%mod;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int pos[1010],cnt,x[210],Y1[210],Y2[210];
int lage(int n,int x[],int y[]){
int ans=0;
for(int i=0;i<cnt;i++){
int up=1,down=1;
for(int j=0;j<cnt;j++){
if(i!=j)up=1ll*up*(n-x[j]+mod)%mod,down=1ll*down*(x[i]-x[j]+mod)%mod;
}
ans=(ans+1ll*up*qpow(down,mod-2)%mod*y[i])%mod;
}
return ans;
}
int main(){
scanf("%d%d",&n,&K);int mx=0;pos[0]++;
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
pos[++pos[0]]=l[i];pos[++pos[0]]=max(0,l[i]-K);
pos[++pos[0]]=r[i];pos[++pos[0]]=max(0,r[i]-K);mx=max(mx,r[i]);
}
pos[++pos[0]]=mx+1;
sort(pos+1,pos+pos[0]+1);pos[0]=unique(pos+1,pos+pos[0]+1)-pos-1;
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<pos[0];i++){
int L=pos[i],R=pos[i]+K;
for(cnt=0;cnt<n+3;cnt++){
if(pos[i]+cnt==pos[i+1])break;
getans(1,L,R);L++;getans(mod-1,L,R);R++;
x[cnt]=pos[i]+cnt;Y1[cnt]=ans1;Y2[cnt]=ans2;
}
if(pos[i]+cnt<pos[i+1]){
ans1=lage(pos[i+1]-1,x,Y1);ans2=lage(pos[i+1]-1,x,Y2);
}
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}