8290

dottle · 2022-04-19 16:00:33 · 个人记录

考虑一个 O(n r) 的计算方法，钦定最小值，则每个数可选择的范围容易计算，可以树形 dp 计算方案数。f_{0/1,i} 代表 i 向子树内延伸的链的数量，g_{0/1,i} 代表这些链的权值和。转移比较简单，不再多提；将链分成两种，直上直下的在深度最浅点处统计答案，其他链在 lca 处统计答案。

考虑如何优化这个过程。我们不妨考虑一种更强的钦定，强制最小值 x 在点 i 处取到，且它是编号最小的值最小的点。这样，其他点的取值方案就是一个与 x 有关的分段函数，每一段都是一次函数。因此，把所有数的断点合在一起，这样数轴会被分成 O(n) 部分，每一部分是至多 n-1 个一次函数的积。而钦定全局最小值方案是钦定每个点为最小值的方案的和，这样说来，原先的限制是一个 n 次左右的函数，因此每段只需计算 O(n) 次点值，总计计算 O(n^2) 次，单次 O(n)，是可以通过的。

而我考场上连第一步都没想到，就开始对着奇怪的东西乱冲，令人感慨。

#include<bits/stdc++.h>
#define int long long
const int N=505,mod=1e9+7;
using namespace std;
using vi=basic_string<int>;

int n,K,m,mx,l[N],r[N];
int dp[2][N],g[2][N];
int res,res1,ans,ans1;
int nwt;
vi imp;

int gsc(int x,int y){
    int ans=1;
    for(int i=1;i<=y;i<<=1,x=x*x%mod)
        if(y&i)
            ans=ans*x%mod;
    return ans;
}int inv(int k){return gsc(k,mod-2);}

#define _to e[i].to
#define fore(k) for(int i=hd[k];i;i=e[i].nx)
struct edge{
    int to,nx;
}e[N];int hd[N],S;
void add(int fr,int to){
    e[++S]=(edge){to,hd[fr]},hd[fr]=S;
}

void Add(int&x,int y){
    x+=y;x%=mod;
}

int Sm(int l,int r){
    return (r-l+1)*(l+r)/2%mod;
}

void dfs(int k,int fa){
    int fl=l[k]<=nwt&&r[k]>=nwt;
    int R=min(r[k],nwt+K),L=max(l[k],nwt);
    int len=max(R-L+1,0ll)-fl;
    dp[1][k]=dp[0][k]=0;
    g[1][k]=g[0][k]=0;
    fore(k)if(_to!=fa){
        dfs(_to,k);
        Add(res,dp[1][k]*dp[0][_to]+dp[0][k]*dp[1][_to]+dp[1][k]*dp[1][_to]);
        Add(res1,dp[1][k]*g[0][_to]+dp[0][k]*g[1][_to]+dp[1][k]*g[1][_to]);
        Add(res1,g[1][k]*dp[0][_to]+g[0][k]*dp[1][_to]+g[1][k]*dp[1][_to]);
        if(L<=R){
            Add(dp[1][k],dp[1][_to]*(len+fl)+dp[0][_to]*fl);
            Add(dp[0][k],dp[0][_to]*len);
            Add(g[1][k],g[1][_to]*(len+fl)+dp[1][_to]*Sm(L,R)+g[0][_to]*fl+dp[0][_to]*L*fl);
            Add(g[0][k],g[0][_to]*len+dp[0][_to]*Sm(L+fl,R));
        }
    }
    Add(dp[1][k],fl);
    Add(dp[0][k],len);
    Add(g[1][k],fl*L);
    if(L<=R)
        Add(g[0][k],Sm(L+fl,R));
    Add(res,dp[1][k]);
    Add(res1,g[1][k]);
}

void calc(int t){
    nwt=t;
    res=0;
    res1=0;
    dfs(1,0);
} 

void push(int k){
    imp+=k,imp+=k-1,imp+=k+1;
}

void solve(int l,int r){
    if(r-l<=m)for(int i=l;i<=r;i++)calc(i),ans+=res,ans1+=res1;
    else {
        vector<int> Y(m),Y1(m);
        calc(l),Y[0]=res,Y1[0]=res1;
        for(int i=1;i<m;i++){
            calc(l+i);
            Y[i]=(Y[i-1]+res)%mod;
            Y1[i]=(Y1[i-1]+res1)%mod;
        }
        for(int i=0;i<m;i++){
            int x=1,y=1;
            for(int j=0;j<m;j++)
                if(i!=j)
                    x=x*(r-l-j)%mod,y=y*(i-j)%mod;
            ans+=Y[i]*x%mod*inv(y)%mod;
            ans1+=Y1[i]*x%mod*inv(y)%mod;
        }
    }
}

main(){
    cin>>n>>K;
    m=n+5;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i],mx=max(mx,r[i]);
        push(l[i]),push(l[i]-K);
        push(r[i]),push(r[i]-K);
    }
    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y),add(y,x);
    }
    sort(imp.begin(),imp.end());
    imp.resize(unique(imp.begin(),imp.end())-imp.begin());
    int pr=1;
    for(auto x:imp){
        solve(pr,x);
        pr=x+1;
    }
    cout<<(ans%mod+mod)%mod<<endl;
    cout<<(ans1%mod+mod)%mod<<endl;
}