脚本宝典收集整理的这篇文章主要介绍了[提高组集训2021] 退钱，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

一、题目

有一棵 (n) 个点的树，根为 (1)，每个点都有一个初始为 (1) 的标记值 (s_i)，对点 (x) 进行操作表示把 (x) 的祖先中深度最小并且 (s_i=1) 的 (i) 置为 (0)，每个叶子有一个操作次数 (a_i)，问有多少种不同的操作序列使得最后标记值全为 (0)

(nleq 10^6)，(sum a_i=n)，保证若 (i) 非叶子则 (a_i=0)

二、解法

我们自底向上考虑，对于每个子树，我们把操作分为两部分，第一部分是操作 (u) 的祖先，第二部分是操作 (u) 的子树，可以知道第一部分的操作全部在第二部分之前，这两者在操作序列上有着不可逾越的鸿沟！

设 (dp[i]) 表示子树 (i) 内的操作序列方案数，考虑怎么把子树内的信息合并上来，发现第一部分内部可以任意安排顺序，第二部分内部也可以任意安排顺序，所以做一个可重集的排列数即可。

三、总结

顺序并不需要一步到位，可以慢慢确定的嘛。

树的问题，可以整体考虑，也可以从小处入手，把问题归结到子树上。

//deep in my bone , straight From inside 
#include <cstdio>
const int M = 1000005;
const int MOD = 1e9+7;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,tot,f[M],a[M],dp[M],siz[M],re[M],fac[M],inv[M];
struct Edge{int v,next;}e[M];
signed main()
{
	freoPEn("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	n=read();
	for(int i=2;i<=n;i++)
	{
		int j=read();
		e[++tot]=edge{i,f[j]},f[j]=tot;
	}
	fac[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		fac[i]=fac[i-1]*i%MOD;
	}
	for(int i=2;i<=n;i++)
		inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD; 
	for(int i=2;i<=n;i++)
		inv[i]=inv[i-1]*inv[i]%MOD;
	for(int u=n;u>=1;u--)
	{
		siz[u]=1;re[u]=a[u]-1;dp[u]=1;
		for(int i=f[u];i;i=e[i].next)
		{
			int v=e[i].v;
			siz[u]+=siz[v];
			re[u]+=re[v];
			dp[u]=dp[u]*dp[v]%MOD
			*inv[siz[v]]%MOD*inv[re[v]]%MOD;
		}
		if(re[u]<0) {puts("0");return 0;}
		dp[u]=dp[u]*fac[siz[u]-1]%MOD*fac[re[u]+1]%MOD;
		if(!f[u]) dp[u]=1;//leaf
	}
	PRintf("%lldn",dp[1]);
}

脚本宝典总结

以上是脚本宝典为你收集整理的[提高组集训2021] 退钱全部内容，希望文章能够帮你解决[提高组集训2021] 退钱所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。