自动搬运

查看原文

来自洛谷，原作者为

	KSCD_ 知不可乎骤得，知来者之可追. | Defection,Retribution,Testify. | Rotating_Catfood

搬运于2025-08-24 22:54:13，当前版本为作者最后更新于2024-08-21 21:27:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

考虑树形 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$。所以这里的方案数由以下几部分组成：

• 从 $a_i$ 个中选出 $k$ 个落入 $to$ 子树。
• 从落入 $to$ 子树的共 $(k+y)$ 个球中选出 $k$ 个作为从 $i$ 释放的，并确定顺序。
• 从落入 $ano$ 子树的共 $(a_i-k+j-y)$ 个球中选出 $(a_i-k)$ 个作为从 $i$ 释放的，并确定顺序。
• 两个子树内部的方案数。

所以对于给定 $(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; 
}