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

· · 题解

[省选联考 2022] 填树

如果不知道拉格朗日插值，其实很难有勇气做下去。因此，本篇题解认为读者已经熟悉拉格朗日插值，并从此角度去考虑问题。

首先，想着复杂度关于 n 的动态规划手足无措时，就会发现这个问题非常依赖值域。说到值域，应当脑中一闪而过拉格朗日插值的想法，在这个方面想下去。

接着会想到枚举一下最小值，就知道了最大值，范围确定下来，是容易 O(n) 动态规划求方案数及和的。不过不久会注意到一个问题，举个例子，[l, r] 和 [l+1, r+1] 两个范围的贡献中，值的范围在 [l+1, r] 中的贡献重复计算两次。不过这个是好处理的，分别计算 [l, r] 和 [l+1, r] 的贡献，从前者中减去后者，就变成了值在 [l, r]，且最小值恰好取到 l，不重不漏。代码参考此。

做了以上的工作，复杂度就是 O(nV) 的了，然后对于一步步枚举最小值计算贡献的操作，就拿拉格朗日插值去优化他。回顾动态规划的过程，当范围连续变化的时候，一个点的单独的方案数是一次函数和常数线段拼起来的，和则是二次函数和常数线段拼起来。这时去找从函数到常数线段的分界点，发现是在当目前枚举到的范围和点的权值范围的边界刚好相交时。因此只需要在这些位置分个段，然后连续的区间做拉格朗日插值就可以了。由于段的个数是 O(n) 的，而单次拉格朗日插值也是 O(n) 的，所以总复杂度 O(n^3)。

Code

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
    res=0; bool f=false; char ch=getchar();
    while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
    while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
    res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int maxn=200;
const int N=maxn+10;
int H[N], edge_cnt, n, m, kn, sum[N], cnt[N], lb, rb, fac[N], inv[N], pre[N], suf[N], d[N<<2], t1[N], t2[N], res1, res2;
//wmr
int moda(int x) { return x>=mod?x-mod:x; }
int mods(int x) { return x<0?x+mod:x; }
struct Edge { int nxt, to; } E[N<<1];
void add(int u, int v) { E[++edge_cnt]={H[u], v}; H[u]=edge_cnt; }
struct node { int l, r; } a[N];
int quick_power(int x, int y) {
    int res=1;
    while (y) {
        if (y&1) res=(ll)res*x%mod;
        x=(ll)x*x%mod, y>>=1;
    }
    return res;
}
//incra
void dfs(int u, int pre) {
    int r=min(rb, a[u].r), l=max(lb, a[u].l);
    if (l>r) l=1, r=0;
    int c0=r-l+1, s0=((ll)(l+r)*(r-l+1)>>1)%mod;
    cnt[u]=c0, sum[u]=s0; res1=moda(res1+c0), res2=moda(res2+s0);
    ACN(i, H[u]) {
        int v=E[i].to;
        if (v==pre) continue;
        dfs(v, u);
        res1=(res1+(ll)cnt[u]*cnt[v])%mod, res2=(res2+(ll)cnt[u]*sum[v]+(ll)cnt[v]*sum[u])%mod;
        cnt[u]=(cnt[u]+(ll)c0*cnt[v])%mod, sum[u]=(sum[u]+(ll)cnt[v]*s0+(ll)c0*sum[v])%mod;
    }
}
int lag(int a[], int m) {
    int ans=0;
    pre[0]=1; L(i, 1, n+2) pre[i]=(ll)pre[i-1]*(m-i)%mod;
    suf[n+3]=1; R(i, n+2, 1) suf[i]=(ll)suf[i+1]*(m-i)%mod;
    L(i, 1, n+2) ans=((ll)a[i]*pre[i-1]%mod*suf[i+1]%mod*inv[i-1]%mod*inv[n+2-i]%mod*(((n+2-i)&1)?mod-1:1)+ans)%mod;
    return ans;
}
//lottle
signed main() {
//  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    fac[0]=1; L(i, 1, maxn+2) fac[i]=(ll)fac[i-1]*i%mod;
    inv[maxn+2]=quick_power(fac[maxn+2], mod-2); R(i, maxn+1, 0) inv[i]=(ll)inv[i+1]*(i+1)%mod;
    rd(n, kn);
    L(i, 1, n) {
        rd(a[i].l, a[i].r);
        d[i*4-3]=a[i].l, d[i*4-2]=max(a[i].l-kn, 0);
        d[i*4-1]=a[i].r, d[i*4]=max(a[i].r-kn, 0);
        d[n*4+1]=max(d[n*4+1], a[i].r+1);
    }
    sort(d+1, d+n*4+2); m=unique(d+1, d+n*4+2)-d-1;
    L(i, 1, n-1) { int u, v; rd(u, v); add(u, v), add(v, u); }
    int ans1=0, ans2=0;
    L(i, 1, m-1) {
        int rc=d[i+1]-d[i], cnt=min(n+2, rc);
        L(j, 1, cnt) {
            lb=d[i]+j, rb=d[i]+j+kn-1; res1=res2=0;
            dfs(1, 0);
            res1=mods(-res1), res2=mods(-res2);
            --lb; dfs(1, 0);
            ans1=moda(ans1+res1), ans2=moda(ans2+res2);
            t1[j]=ans1, t2[j]=ans2;
        }
        if (rc<=n+2) continue;
        ans1=lag(t1, rc), ans2=lag(t2, rc);
    }
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}