#C241105A. 树上的数(treei)

标签（Label）

动态规划（树形dp）

前言（Front talk）

明明状态都设的是对的，但是就是没想到转移？

网址（Website）

题目详情 - 树上的数(treei) - Super

题解 - 树上的数(treei) - Super

题目（Problem）

样例

输入数据 1

5 
1 1 2 2 
1 2 0 0 1

输出数据 1

【样例 1 解释】

$1\sim n$ 号点染的颜色可以分别是： $[1,2,2,2,5], [1,2,4,2,5], [1,2,5,2,5], [2,2,1,2,5], [3,2,1,2,5], [4,2,1,2,5], [5,2,1,2,5]$ 。

输入数据 2

8 
1 1 2 1 3 2 4 
3 1 0 1 0 0 0 0

输出数据 2

【样例3】

见附件中的 treei/treei3.in 与 treei/treei3.out。该样例满足测试点 $8∼11$ 的限制。

样例下载

题解（Solution）

$\qquad$当时为什么没有想出来呢？

$\qquad$根本没有去思考 $f_{x,j}$ 的初始值，导致后面根本没有推出来。

$\qquad$最重要的：初值为 $f(x, 0) = n - d_x, f(x, 1) = 1$。

出题者题解

算法分析

签到题，知道对空位 $dp$ 就不难了。

1.1 算法1

搜索每个点上填的数, 期望得分 $10$ 分。

1.2 算法2

当 $b_i = 0$ 时, 若 $i$ 号点的深度为 $d_i$ (根的深度为 1 ), 它上面的数不能与任何祖先的编号相同, 所以有 $n - d_i$ 种选择。因此答案是 $\prod (n - d_i)$。期望得分 $10$ 分, 结合算法一期望得分 $20$ 分。

1.3 算法3

算法二提示我们, 每个点如果强制不对祖先造成贡献, 方案数是容易计算的。但是如果要对祖先造成贡献, 就不方便直接在自己处计算，所以考虑留到祖先处再计算。

设 $f(i, j)$ 表示 $i$ 的子树内有 $j$ 个空位的方案数, “空位” 的含义是预留起来要给祖先造成贡献, 还未确定具体填什么的点。

初值为 $f(x, 0) = n - d_x, f(x, 1) = 1$。合并子树时, 就是在 $j$ 一维做卷积；计算完 $x$ 的子树后, 令 $f(x, k)\binom{k}{b_x} \rightarrow f’(x, k - b_x)$，表示用掉一些空位。

时间复杂度 $O(n^2)$，期望得分 $100$ 分。

代码（Code）

#include<bits/stdc++.h>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++) 
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 5005;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
int bas[N], inv[N];
inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod,k>>=1;
	}return res;
}inline int C(int n,int m){
	if(n==0||m==0||n<=m) return 1;
	return bas[n]*inv[m]%mod*inv[n-m]%mod;
}

vector<int> ft[N];
int f[N][N];
int n,b[N];

int siz[N],dep[N],g[N];
void dfs(int x,int fa){
	dep[x] = dep[fa]+1, siz[x] = 1;
	f[x][0] = n-dep[x], f[x][1] = 1;
	for(auto y:ft[x]){
		dfs(y,x);
		For(i,0,siz[x]) For(j,0,siz[y]){
			add(g[i+j], f[x][i]*f[y][j]%mod);
		}siz[x] += siz[y];
		For(i,0,siz[x]) f[x][i]=g[i],g[i]=0;
	}For(i,b[x],siz[x]) g[i-b[x]] = f[x][i]*C(i,b[x])%mod;
	For(i,0,siz[x]) f[x][i] = g[i], g[i]=0;
}

void Solve(){
	cin>>n;For(x,2,n){
		int y=rd();ft[y].emplace_back(x);
	}For(i,1,n) b[i]=rd();
	dfs(1,0), cout<<f[1][0]<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("treei.in","r",stdin);
	freopen("treei.out","w",stdout);
	int T=1;double Tim = clock();
	bas[0]=1;For(i,1,N-5) bas[i]=bas[i-1]*i%mod;
	inv[N-5] = ksm(bas[N-5],mod-2);
	Rof(i,N-6,1) inv[i] = inv[i+1]*(i+1)%mod;
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}