题解：P8290 [省选联考 2022] 填树

· · 题解

首先不难想到一个 \mathcal O(nk) 的树形 DP。

首先枚举最小值 w，设 f_{x,0/1} 表示在 x 子树中，不存在/存在权值为 w 的点，且所有点的权值都在 [w,w+K] 中时，x 向下的合法链个数，g_{x,0/1} 为这些合法链的权值和。转移是简单的，代码如下：

bool Inc(int l,int r){return l<=mn&&mn<=r;}
int Inter(int l,int r){return max(0ll,min(r,mn+K)-max(l,mn)+1);}
int InterSum(int l,int r){
    l=max(l,mn),r=min(r,mn+K);
    if(l>r)return 0;
    return (l+r)*(r-l+1)/2%MOD;
}
void DP(int x,int fa){
    f[x][1]=Inc(l[x],r[x]);
    g[x][1]=Inc(l[x],r[x])*mn;
    f[x][0]=Inter(l[x],r[x])-f[x][1];
    g[x][0]=InterSum(l[x],r[x])-g[x][1];
    int v1=f[x][1],v0=f[x][0],g1=g[x][1],g0=g[x][0];
    (ans1+=f[x][1])%=MOD;
    (ans2+=g[x][1])%=MOD;
    for(int y:ed[x]){
        if(y==fa)continue;
        DP(y,x);
        (ans1+=f[x][1]*f[y][0]+f[x][1]*f[y][1]+f[x][0]*f[y][1])%=MOD;
        (ans2+=g[x][1]*f[y][0]+g[x][1]*f[y][1]+g[x][0]*f[y][1]+
               f[x][1]*g[y][0]+f[x][1]*g[y][1]+f[x][0]*g[y][1])%=MOD;
        (g[x][1]+=v1*g[y][0]+v1*g[y][1]+v0*g[y][1]+
                  g1*f[y][0]+g1*f[y][1]+g0*f[y][1])%=MOD;
        (g[x][0]+=v0*g[y][0]+g0*f[y][0])%=MOD;
        (f[x][1]+=v1*f[y][0]+v1*f[y][1]+v0*f[y][1])%=MOD;
        (f[x][0]+=v0*f[y][0])%=MOD;
    }
    return;
}

虽然这样会做 \mathcal O(K) 次 DP，但这些 DP 的转移是不变的，变化的是一些点的初始状态，我们去探究其规律。

将 \min(r,w+K),\max(l,w) 中的 \min,\max 拆开，我们发现每个点 f,g 的初始状态分别是关于 w 的一次和二次函数，所以最终乘起来后，ans1,ans2 分别是关于 w 的 n 次与 n+1 次函数。我们要求的是函数取到 [1,K] 的和，而 k 次多项式的和为 k+1 次多项式，注意到多项式函数定义域大，次数小，我们可以直接拉格朗日插值解决！

最终复杂度 \mathcal O(n^3)。

完整代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int NN=805,MOD=1e9+7;
int n,K;
int f[NN][2],l[NN],r[NN],mn,ans1,ans2,mxr,fans,g[NN][2];
vector<int> ed[NN];
bool Inc(int l,int r){return l<=mn&&mn<=r;}
int Inter(int l,int r){return max(0ll,min(r,mn+K)-max(l,mn)+1);}
int InterSum(int l,int r){
    l=max(l,mn),r=min(r,mn+K);
    if(l>r)return 0;
    return (l+r)*(r-l+1)/2%MOD;
}
int QP(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*c*a%MOD;
        a=1ll*a*a%MOD;
    }
    return c;
}
void DP(int x,int fa){
    f[x][1]=Inc(l[x],r[x]);
    g[x][1]=Inc(l[x],r[x])*mn;
    f[x][0]=Inter(l[x],r[x])-f[x][1];
    g[x][0]=InterSum(l[x],r[x])-g[x][1];
    int v1=f[x][1],v0=f[x][0],g1=g[x][1],g0=g[x][0];
    (ans1+=f[x][1])%=MOD;
    (ans2+=g[x][1])%=MOD;
    for(int y:ed[x]){
        if(y==fa)continue;
        DP(y,x);
        (ans1+=f[x][1]*f[y][0]+f[x][1]*f[y][1]+f[x][0]*f[y][1])%=MOD;
        (ans2+=g[x][1]*f[y][0]+g[x][1]*f[y][1]+g[x][0]*f[y][1]+
               f[x][1]*g[y][0]+f[x][1]*g[y][1]+f[x][0]*g[y][1])%=MOD;
        (g[x][1]+=v1*g[y][0]+v1*g[y][1]+v0*g[y][1]+
                  g1*f[y][0]+g1*f[y][1]+g0*f[y][1])%=MOD;
        (g[x][0]+=v0*g[y][0]+g0*f[y][0])%=MOD;
        (f[x][1]+=v1*f[y][0]+v1*f[y][1]+v0*f[y][1])%=MOD;
        (f[x][0]+=v0*f[y][0])%=MOD;
    }
    return;
}
int lsh[NN];
typedef pair<int,int> pa;
#define x first
#define y second
vector<pa> v1,v2;
int F(int X,vector<pa>&v){
    int val=0;
    for(int i=0;i<v.size();i++){
        int prod1=1,prod2=1;
        for(int j=0;j<v.size();j++){
            if(i==j)continue;
            (prod1*=X-v[j].x)%=MOD;
            (prod2*=v[i].x-v[j].x)%=MOD;
        }
        (val+=v[i].y*prod1%MOD*QP(prod2,MOD-2))%=MOD;
    }
    return val;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        mxr=max(mxr,r[i]);
        lsh[++lsh[0]]=l[i],lsh[++lsh[0]]=max(1ll,r[i]-K);
        lsh[++lsh[0]]=r[i],lsh[++lsh[0]]=max(1ll,l[i]-K);
    }
    lsh[++lsh[0]]=mxr+1;lsh[++lsh[0]]=1;
    sort(lsh+1,lsh+1+lsh[0]);
    lsh[0]=unique(lsh+1,lsh+1+lsh[0])-lsh-1;
    for(int i=1;i<n;i++){
        int l,r;cin>>l>>r;
        ed[l].push_back(r);
        ed[r].push_back(l);
    }
    for(int i=1;i<lsh[0];i++){
        v1.clear();v2.clear();
        for(mn=lsh[i];mn<=min(lsh[i]+n+4,lsh[i+1]-1);mn++){
            DP(1,1);
            v1.push_back({mn,ans1});
            v2.push_back({mn,ans2});
        }
        ans1=F(lsh[i+1]-1,v1);
        ans2=F(lsh[i+1]-1,v2);
    }
    cout<<ans1<<"\n"<<ans2%MOD;
    return 0;
}