P10053 题解

· · 题解

思路

考虑树形 DP，提前处理出每个结点处释放的球数 a_i，以每个点为根的子树大小 siz_i，以每个点为根的子树内释放的球数 cnt_i。以下记 K 为总球数，b_i 表示 i 子树内最多能容纳的外部球数，b_i=siz_i-cnt_i。

设 f_{i,j} 表示以 i 为根的子树内由其父亲落入了 j 个球的方案数，有意义的 j 满足 j\le K-cnt_i 且 j\le b_i。这里还需要详细定义以避免算重，也就是说每个点只被确定一次顺序。

因此我们在处理 f_i 时确定在 i 处释放的球的先后顺序，可以避免算重。所以 f_{i,j} 的定义变为只考虑 j 个最终位置点集的方案数，也可以说暂时认为这些球是相同的，无先后顺序。这样做的本质是把所有球按释放位置分组，先确定每一组所占的位置集合，然后再在组内排列确定顺序，不会计重。

考虑转移，首先发现这 j 个球在落入 i 时一定已经确定之后优先走的子树，这取决于 i 是其父亲的哪个儿子，需要记录，在 DFS 里用参数记下来即可。我们此处设 to 为优先走的子树根，ano 为另一个子树根，没有则为 0。

另外还要确定的就是在 i 处释放的 a_i 个球的方向，考虑枚举其落入 to 子树的球数 k，有意义的 k 满足 k\le b_{to} 且 k\le a_i，剩余的 (a_i-k) 个球落入 ano 子树。

那么从父亲来的 j 个球就可能会由于 to 子树被填满而去 ano 子树，会剩下 y=\min(j,b_{to}-k) 个球真正落入了 to 子树，另外 (j-y) 个落入 ano 子树。

由于从父亲来的 j 个球没有区别，选择 y 个的方案数为 1。所以这里的方案数由以下几部分组成：

所以对于给定 (j,k) 的方案数为：\binom{a_i}{k}\times A_{k+y}^k\times A_{a_i-k+j-y}^{a_i-k}\times f_{to,k+y}\times f_{ano,a_i-k+j-y-flag}，其中 A 为排列数， flag=[j=b_i]，即如果 j 个球落入后把 i 子树填满了，则最后一个球会留在 i 点，不会落入 ano 子树，需要减去。

最终把所有 k 算出的方案数累加起来，便为 f_{i,j} 的最终值，最终答案为 f_{1,0}。另有很多边界问题，这里只需要保证所有无法达到的 (i,j) 满足 f_{i,j}=0 即可，因此初值为空树的 f_{0,0}=1，其余为 0。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=4e3+10,mod=1e9+7;
int po(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod,b>>=1; 
    }    
    return res;
}
int fr[N],ifr[N];
int C(int n,int m) {return fr[n]*ifr[m]%mod*ifr[n-m]%mod;}
int A(int n,int m) {return fr[n]*ifr[n-m]%mod;}
int temp,n,kk,a[N],b[N],l[N],r[N],siz[N],cnt[N],f[N][N];
void dfs(int i,bool lr)
{
    int lc=l[i],rc=r[i];
    if(lc) dfs(lc,1);
    if(rc) dfs(rc,0);
    siz[i]=siz[lc]+siz[rc]+1,cnt[i]=cnt[lc]+cnt[rc]+a[i],b[i]=siz[i]-cnt[i];
    for(int j=0;j<=b[i]&&j<=kk-cnt[i];j++)
    {
        int to=(lr?lc:rc),ano=(lr?rc:lc);
        for(int k=0;k<=b[to]&&k<=a[i];k++) 
        {
            int y=min(j,b[to]-k),flag=(j==b[i]);
            int ta=f[to][k+y]*A(k+y,k)%mod,tb=f[ano][a[i]-k+j-y-flag]*A(a[i]-k+j-y,a[i]-k)%mod;
            f[i][j]=(f[i][j]+C(a[i],k)*ta%mod*tb%mod)%mod;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>kk,fr[0]=ifr[0]=f[0][0]=1;
    for(int i=1;i<=n;i++) fr[i]=fr[i-1]*i%mod,ifr[i]=po(fr[i],mod-2);
    for(int i=1;i<=kk;i++) cin>>temp,a[temp]++;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    dfs(1,0),cout<<f[1][0];
    return 0; 
}