【第七届图灵杯高级组】A. 棋无常树 做题记录

给定一棵 $n$ 个点的以 $1$ 为根的有根树，点 $u$ 有权值 $a_i$ 和 $b_i$。定义树合法当且仅当每个点 $u$ 都满足其子树内 $a_i$ 的 $\text{mex}$ 为 $b_i$。

有些 $b_u=-1$ 表示点 $u$ 没有限制，还有些 $a_u=-1$ 表示 $a_u$ 可以在 $[0,n]$ 中任选。求有多少种给所有 $a_u=-1$ 的 $a_u$ 赋值的方案使得树是合法的，对 $10^9+7$ 取模。

$1\le n\le 5000$，$-1\le a_u,b_u\le n$。

首先设 $mx_u$ 表示 $u$ 子树内 $b$ 的最大值，则若 $b_u\not=-1$ 且 $b_u<mx_u$ 那么一定无解。

刚开始设的状态是 $f_{u,0/1,i}$ 表示 $u$ 的子树，确定 $\le mx_u$ 的 $a$ 都填完了，是否有 $=mx_u$ 的 $a$，$> mx_u$ 的还未确定的 $a$ 有 $i$ 个的方案数，可是这样由于有容斥所以我不会优化，只能做到 $O(n^3)$。

考虑设 $vis_{u,i}$ 表示 $u$ 子树内 $i$ 是否确定出现，则一个数 $x$ 确定出现当且仅当子树内有某个 $a_v=x$ 或 $x<mx_u$。

设 $f_{u,0/1,i}$ 表示 $u$ 的子树，（$a$ 中）确定出现过的数都填完了，是否有 $=mx_u$ 的数，共填了 $i$ 种未确定出现过的数，且这 $i$ 种数的大小顺序还未确定的方案数。

考虑合并子树的过程，首先对于 $vis_{u,x}=1,vis_{v,x}=0$ 的数 $x$，$v$ 子树中可能有一种未确定出现过的数为 $x$，所以滚一次背包；对于 $vis_{u,x}=0,vis_{v,x}=1$ 的数同理。

接下来要处理两颗子树中都未出现过，但相同的数，也是直接滚背包，即看一下 $v$ 子树中未确定出现的数是否有一种和 $u$ 子树中第 $i$ 种未确定的数相同。

做完这些处理之后直接卷积即可，注意滚背包的时候要乘系数，即从 $i$ 种数中选一种出来配对，系数为 $i$。

最后再把 $vis$ 合并一下。

但是考虑已经合并进 $u$ 的某个儿子 $v$，在合并新的儿子 $v'$ 时，$mx_v$ 这个数比较特殊，即使 $vis_{u,mx_v}=0,vis_{v',mx_v}=1$ 也不能有 $v$ 子树中未确定出现过的数“雪藏”在这里，而我们的状态中并未记录相关信息。所以需要将儿子按照 $mx_v$ 从大到小的顺序合并。

最后若 $b_u\not=-1$ 则要将 $\text{mex}$ 推上去，即选一些未确定的数出来填了。

时间复杂度就是树上背包的复杂度，即 $O(n^2)$。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int S=5005;

#define p 1000000007

int fra[S],C[S][S];
int n,a[S],b[S],fa[S];
bool vis[S][S];
vector<int> son[S];
int tu[S],tv[S],tmp[S],h[2][S],th[2][S];
int siz[S],f[S][2][S];

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}

int main()
{
	for(int i=0;i<=S-3;i++)
	{
		fra[i]=(i==0?1:1ll*fra[i-1]*i%p);
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
	}
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	fa[1]=0;
	for(int i=2;i<=n;i++) cin>>fa[i],son[fa[i]].push_back(i);
	for(int u=n;u>=1;u--)
	{
		sort(son[u].begin(),son[u].end(),[&](int x,int y){return b[x]>b[y];});
		int lb=-1;
		for(int v:son[u]) lb=max(lb,b[v]);
		siz[u]=1;
		memset(h,0,sizeof(h));
		if(a[u]!=-1) vis[u][a[u]]=true,h[a[u]==lb][0]=1;
		else
		{
			h[0][1]=1;
			if(lb!=-1) h[1][0]=1;
		}
		for(int v:son[u])
		{
			auto doit=[&](int id,int vt,bool has){
				memcpy(tu,h[id],sizeof(h[id]));
				memset(tv,0,sizeof(tv));
				if(vt&1) for(int i=0;i<=siz[v];i++) add(tv[i],f[v][0][i]);
				if(vt&2) for(int i=0;i<=siz[v];i++) add(tv[i],f[v][1][i]);
				memset(tmp,0,sizeof(tmp));
				if(lb!=-1&&!has&&vis[v][lb]) return;
				for(int i=0;i<=n;i++)
					if(i==lb)
					{
						if(vt==3&&has&&!vis[v][i])
							for(int j=1;j<=siz[v];j++) tv[j-1]=1ll*tv[j]*j%p,tv[j]=0;
					}
					else
					{
						if(vis[u][i]==vis[v][i]) continue;
						if(!vis[u][i])
							for(int j=1;j<=siz[u];j++) add(tu[j-1],1ll*tu[j]*j%p);
						if(!vis[v][i]&&i!=b[v])
							for(int j=1;j<=siz[v];j++) add(tv[j-1],1ll*tv[j]*j%p);
					}
				for(int i=0;i<=siz[u];i++)
				{
					for(int j=0;j<=siz[v];j++)
						add(tmp[i+j],1ll*tu[i]*tv[j]%p);
					for(int j=1;j<=siz[v];j++)
						add(tv[j-1],1ll*tv[j]*j%p);
				}
			};
			memset(th,0,sizeof(th));
			if(lb==-1||b[v]!=lb)
			{
				if(lb==-1||!vis[u][lb])
				{// 0->0
					doit(0,3,false);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[0][i],tmp[i]);
				}
				if(lb!=-1)
				{// 0->1
					doit(0,3,true);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
				}
				{// 1->1
					doit(1,3,false);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
					doit(1,3,true);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
				}
			}
			else
			{
				if(lb==-1||!vis[u][lb])
				{// 0->0
					doit(0,1,false);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[0][i],tmp[i]);
				}
				if(lb!=-1)
				{// 0->1
					doit(0,2,true);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
				}
				{// 1->1
					doit(1,1,false);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
					doit(1,2,true);
					for(int i=0;i<=siz[u]+siz[v];i++) add(th[1][i],tmp[i]);
				}
			}
			memcpy(h,th,sizeof(h));
			for(int i=0;i<=n;i++) vis[u][i]|=vis[v][i];
			siz[u]+=siz[v];
		}
		if(b[u]==lb)
			for(int i=0;i<=siz[u];i++) f[u][0][i]=h[0][i];
		else if(b[u]==-1)
			for(int i=0;i<=siz[u];i++)
				add(f[u][0][i],h[0][i]),
				add(f[u][1][i],h[1][i]);
		else
		{
			int cnt=0;
			for(int i=lb+1;i<b[u];i++) cnt+=!vis[u][i];
			if(vis[u][lb])
				for(int i=cnt;i<=siz[u];i++)
					add(f[u][0][i-cnt],1ll*h[0][i]*C[i][cnt]%p*fra[cnt]%p),
					add(f[u][0][i-cnt],1ll*h[1][i]*C[i][cnt]%p*fra[cnt]%p);
			else
				for(int i=cnt;i<=siz[u];i++)
					add(f[u][0][i-cnt],1ll*h[lb!=-1][i]*C[i][cnt]%p*fra[cnt]%p);
		}
		if(b[u]!=-1&&vis[u][b[u]]) return cout<<"0\n",0;
		b[u]=max(b[u],lb);
		for(int i=0;i<b[u];i++) vis[u][i]=true;
	}
	int cnt=n-b[1];
	for(int i=b[1]+1;i<=n;i++) cnt-=vis[1][i];
	int ans=0;
	for(int i=0;i<=siz[1];i++)
		add(ans,1ll*(f[1][0][i]+f[1][1][i])*C[cnt][i]%p*fra[i]%p);
	cout<<ans<<'\n';
	return 0;
}
/*
vis[u][i]=1 且 vis[v][i]=0 的怎么合并
f[u][i] 表示 u 子树，填完了必定出现的值，有 i 种未确定的未出现的值
	 - que1：这 i 种值顺序确定好了吗
		没确定好
*/