2020牛客暑期多校训练营Operating on the Tree(树形DP，组合数学)

Operating on the Tree

题目描述

输入描述:

输出描述:

示例1

输入

3
4
0 1 2
4
0 1 1
2
0

输出

48
60
2

说明

题目大意

这道题是从同一场的G题改过来的（顺手骗一下访问量，G题题解），给定一棵树。每个节点会有不同的颜色(即1 ~ n)，然后又是很玄幻的建边。现有一个操作序列$p$p，按其顺序对树进行颜色的扩张染色(具体可以看上面G题题解里有详细的简绍)，如果对于$p_i$pi​，在当前的树上能找到这种颜色并染色，那么我们称这个操作是成功的，否则是失败的。
要求你对于$p\{1,2,...,n\}$p{1,2,...,n}的每种排列，都求出每个操作序列里成功的操作数，并求和输出。

分析

嗯……题目有点绕，让我们找个简单的例子来试试。

嗯，这个够简单了吧。首先我们拿一个序列来试水：
$p=\{1,2,3\}$p={1,2,3}，那么一次操作后，1把它周围的点全部染成了1，此时1是成功的，对于2,3的操作是失败的。所以$p=\{1,2,3\}$p={1,2,3}的答案是1。
同样的，若$p=\{2,1,3\}$p={2,1,3}，那么答案是2，因为2和3均可以做到染色。

一下列出所有的$p$p。
$\{1,2,3\}=1${1,2,3}=1$\qquad$$\{1,3,2\}=1${1,3,2}=1$\qquad$$\{2,1,3\}=2${2,1,3}=2
$\{2,3,1\}=2${2,3,1}=2$\qquad$$\{3,1,2\}=2${3,1,2}=2$\qquad$$\{3,2,1\}=2${3,2,1}=2
所以对于上面的那棵树，$ans=1+1+2+2+2+2=10$ans=1+1+2+2+2+2=10。

接下来我们回顾一下刚刚的过程，如果1成功了，那么2,3都失败，如果1失败，那么2,3可以成功，可以失败，至少会有一个成功。看着眼熟吗？嗯就是树形dp的入门必刷题Anniversary party(这些日子VOJ又不行了)。那么我们可以通过父节点的成功与否，来传递子节点的成功与否。

首先定义dp的含义。
$dp[i][sta][j]$dp[i][sta][j]表示第$i$i个节点在$sta$sta状态下，子树大小为$j$j时，有多少种方案。欸，虽然是两道差不多的题，这题的转移可是麻烦的很！

首先考虑$sta$sta，它的值是0,1,2表示失败，成功，将要失败。则设子状态的子树大小为$k$k。有
$dp[i][0][j]=所有子状态至少一个为成功$dp[i][0][j]=所有子状态至少一个为成功
$dp[i][1][j]=dp[son][0][k]$dp[i][1][j]=dp[son][0][k]
$dp[i][2][j]=父节点为成功$dp[i][2][j]=父节点为成功
这就是比较伪的代码(是真的伪)¹

具体的请看代码(这好像不太对，不是技穷的时候搪塞用的吗)，具体dfs里的注释xinjun讲得更好，可以看看。（主要是怕自己看的不是很透彻然后写错）

代码

#include<bits/stdc++.h>
#define ll long long
#define inf 1<<30
using namespace std;
const int MAXN=2e3+10;
const int mod=998244353;
int dp1[MAXN][3][MAXN],dp2[MAXN][3][MAXN];//dp
// 0 -> good 1 -> bad, adjacent to good 2 -> bad, not adjacent to good
int tmp1[3][MAXN],tmp2[3][MAXN];
int siz[MAXN],C[MAXN][MAXN];//组合数和子树大小
vector<int> e[MAXN];//边
void admod(int &a,int b){a=((a+b)>=mod)?(a+b-mod):(a+b);}//带mod的加法用此方法，更快
void dfs(int pos){//是的，树形dp就是这么残忍
	siz[pos]=1;dp1[pos][0][0]=dp1[pos][2][0]=1;
	for(int _=0;_<e[pos].size();_++){
		int s=e[pos][_];dfs(s);
		for(int i=0;i<3;i++)//更新dp的值为前缀和，便于后续计算。注：此时dp含义已经变化，dp[i][sta][j]变成了最多j个节点比i大时的情况
			for(int j=1;j<siz[s];j++)
				admod(dp1[s][i][j],dp1[s][i][j-1]),admod(dp2[s][i][j],dp2[s][i][j-1]);
		for(int i=0;i<siz[pos];i++)
			for(int j=0;j<=siz[s];j++){
				int coe=1ll*C[i+j][j]*C[siz[pos]-i-1+siz[s]-j][siz[s]-j]%mod;
				for(int t1=0;t1<3;t1++)
					for(int t2=0;t2<3;t2++){
						int cnt=j?dp1[s][t2][j-1]:0,cnt1=j?dp2[s][t2][j-1]:0;
						int coe1=1ll*coe*dp1[pos][t1][i]%mod*cnt%mod;
						int base=1ll*coe*(1ll*dp1[pos][t1][i]*cnt1%mod+1ll*dp2[pos][t1][i]*cnt%mod)%mod;
						
						if(t1==0&&t2==1) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
						else if(t1==1&&(t2==0||t2==1)) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
						else if(t1==2&&t2==0) admod(tmp1[1][i+j],coe1),admod(tmp2[1][i+j],base);
						else if(t1==2&&t2==1) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
						
						cnt=(dp1[s][t2][siz[s]-1]-cnt+mod)%mod;
						cnt1=(dp2[s][t2][siz[s]-1]-cnt1+mod)%mod;
						coe1=1ll*coe*dp1[pos][t1][i]%mod*cnt%mod;
						base=1ll*coe*(1ll*dp1[pos][t1][i]*cnt1%mod+1ll*dp2[pos][t1][i]*cnt%mod)%mod;
						
						if(t1==0&&(t2==1||t2==2)) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
						if(t1==1&&(t2==1||t2==0)) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
						if(t1==2&&(t2==1||t2==0)) admod(tmp1[t1][i+j],coe1),admod(tmp2[t1][i+j],base);
					}
			}siz[pos]+=siz[s];
		for(int i=0;i<siz[pos];i++)
			for(int j=0;j<3;j++)
				dp1[pos][j][i]=tmp1[j][i],dp2[pos][j][i]=tmp2[j][i],
				tmp1[j][i]=tmp2[j][i]=0;
	}for(int i=0;i<siz[pos];i++) admod(dp2[pos][0][i],dp1[pos][0][i]);
}
int main()
{
	for(int i=0;i<MAXN;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}//杨辉三角算组合数
	int t,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0;i<=n;i++)
			e[i].clear(),
			memset(dp1[i],0,sizeof(dp1[i])),
			memset(dp2[i],0,sizeof(dp2[i]));//初始化，只要初始化大小为n的就行
//我debug的经历又一次生动地告诉我们拒绝骚操作
		for(int i=2,f;i<=n;i++)
			scanf("%d",&f),++f,e[f].push_back(i);//玄幻存边
		dfs(1); int ans=0;
		for(int i=0;i<n;i++)
			admod(ans,dp2[1][0][i]),admod(ans,dp2[1][1][i]);
		printf("%d\n",ans);
	}
}

END

……这题真的有点烦，尤其是发现辛辛苦苦打完后发现(嗯？没过样例？？)然后从头到尾检查一遍的感受，是不可言传的。

---

1. 蒟蒻写得匆忙，没有仔细，如有错望各位看官谅解。 ↩︎