题解P8329 [ZJOI2022] 树
Umbrella_Leaf
2022-05-06 21:17:53
### 分析
> 设 $f(S)$ 表示第一棵树的非叶子集合**恰好**为 $S$ 时构造第一棵树的方案数。
>
> 设 $g(T)$ 表示第二棵树的非叶子集合**恰好**为 $T$ 时构造第二棵树的方案数。
那么答案为
$$Ans=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)$$
直接求这个不太好求，我们考虑容斥。
> 设 $f'(S)$ 表示第一棵树的非叶子集合**包含于** $S$ 时构造第一棵树的方案数。
>
> 设 $g'(T)$ 表示第二棵树的非叶子集合**包含于** $T$ 时构造第二棵树的方案数。
$$
\begin{aligned}
Ans&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}f(S)g(T)\\&=\sum_{S\cap T=\varnothing,S\cup T=\{1,2,\cdots,n\}}\sum_{S'\subseteq S,T'\subseteq T}f'(S')g'(T')(-1)^{|S|-|S'|+|T|-|T'|}
\\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-1)^{n-|S'|-|T'|}2^{n-|S'|-|T'|}\\&=\sum_{S'\cap T'=\varnothing}f'(S')g'(T')(-2)^{n-|S'|-|T'|}
\end{aligned}
$$
其中倒数第二个等号的理由是：不属于 $S'$ 和 $T'$ 的那些元素可能在 $S$ 中，也可能在 $T$ 中。
然后可以 DP，我们设 $dp_{i,j,k}$ 表示确定了 $[1,i]$ 中的点在 $S'$ 和 $T'$ 中的情况，$|\{1,\cdots,i\}\cap S'|=j$，$|\{i+1,\cdots,n\}\cap T'|=k$ ，且我们已经为 $(1,i]$ 选好了第一棵树中的父亲，为 $[1,i)$ 选好了第二棵树中的父亲时，这些父亲的方案数。
初值：$\forall k\in[1,n)$，$dp_{1,1,k}=1$。因为 $1$ 一定是第一棵树的非叶子节点，也一定是第二棵树的叶子节点，不需要对其进行容斥。
转移时，分类讨论 $i$ 在 $S'$ 和 $T'$ 中的情况，然后确定 $i$ 在第一棵树中的父亲和 $i-1$ 在第二棵树中的父亲：
1. $i$ 属于 $S'$，$dp_{i-1,j,k}$ 转移到 $dp_{i,j+1,k}$，系数为 $j\times k$
2. $i$ 属于 $T'$，$dp_{i-1,j,k}$ 转移到 $dp_{i,j,k-1}$，系数为 $j\times k$
3. $i$ 两个都不属于，$dp_{i-1,j,k}$ 转移到 $dp_{i,j,k}$，系数为 $-2\times j\times k$
其中转移系数中包含 $j\times k$ 的原因是：
> 考虑对于一个 $S$，如何计算 $f'(S)$。
>
> 对于节点 $i\in(1,n]$，$fa_i$ 可能是 $[1,i)$ 中的任意一个非叶子节点下面，那么方案数是 $[1,i)$ 中非叶子节点的个数，也就是 $j$。
>
> $g'(T)$ 同理，只不过此时我们计算的是 $i-1$ 在第二棵树中的父亲方案数，也就是 $[i,n]$ 中非叶子节点的个数。
>
> 根据乘法原理，只需要将所有这样的点个数乘起来即可。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;ll mod;
ll dp[2][505][505];
int main(){
scanf("%d%lld",&n,&mod);
for(int i=1;i<n;i++)dp[1][1][i]=1;
for(int i=2,now=0;i<=n;i++,now^=1){
memset(dp[now],0,sizeof(dp[now]));
ll ans=0;
for(int j=1;j<i;j++)
for(int k=1;k<=n-i+1;k++)if(dp[now^1][j][k]){
dp[now][j][k]=(dp[now][j][k]+dp[now^1][j][k]*(mod-2)%mod*j%mod*k%mod)%mod;
dp[now][j+1][k]=(dp[now][j+1][k]+dp[now^1][j][k]*j%mod*k%mod)%mod;
dp[now][j][k-1]=(dp[now][j][k-1]+dp[now^1][j][k]*j%mod*k%mod)%mod;
if(k==1)ans=(ans+dp[now^1][j][k]*j%mod*k%mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
```