CF1146F Leaf Partition 树形DP

感觉很多树上难以直接求解的问题都可以转化为动态规划问题并进行求解$.$
令 $f[x],g[x]$ 分别表示以 $x$ 为根的子树不想上延申，向上延申的方案数$.$
这里向上延申指的是会有其他子树的节点与该点子树中某个点颜色相同并进行配对$.$
考虑转移：
$f[x]=g[x]=\prod_{v\in son[x]} (f[v]+g[v]).$
然而，我们还要减掉一些不合法的.
令 $v'$ 表示我们当前枚举到的儿子.
先考虑 $f[x]:$
首先，$x$ 儿子中不可能只有一个延申：$f[x]$ 已经表示在 $x$ 终止了，而只有一个延申的话不能在 $x$ 终止.
所以，$f[x]=\prod_{v\in son[x]} (f[v]+g[v])-\frac{\prod_{v\in son[x]}f[v]}{f[v']}\times g[v'].$
而 $g[x]$ 中不能出现一个都不延申的情况，即 $g[x]=\prod_{v\in son[x]} (f[v]+g[v])-\prod_{v\in son[x]}f[v].$

#include <cstdio>

#include <algorithm>

#define N 200005

#define mod 998244353

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

ll qpow(ll base,ll k)

{

	ll tmp=1;

	for(;k;base=base*base%mod,k>>=1) if(k&1) tmp=tmp*base%mod;

	return tmp;

}

ll inv(ll k)

{

	return qpow(k,mod-2);

}

int n,edges;

ll f[N],g[N];

int hd[N],to[N],nex[N],size[N];

void add(int u,int v)

{

	nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;

}

void dfs(int u)

{

	int i;

	size[u]=1;

	ll sum=1;

	f[u]=g[u]=1;

	for(i=hd[u];i;i=nex[i])

	{

		int v=to[i];

		dfs(v);

		size[u]+=size[v];

		sum=sum*f[v]%mod;

		f[u]=f[u]*((f[v]+g[v])%mod)%mod;

	}

	g[u]=f[u];

	if(size[u]>1)

	{

		g[u]=(g[u]+mod-sum)%mod;

		for(i=hd[u];i;i=nex[i])

		{

			int v=to[i];

			ll tmp=inv(f[v])*g[v]%mod;

			tmp=tmp*sum%mod;

			f[u]=(f[u]+mod-tmp)%mod;

		}

	}

}

int main()

{

	int i,j;

	// setIO("input");

	scanf("%d",&n);

	for(i=2;i<=n;++i)

	{

		int a;

		scanf("%d",&a),add(a,i);

	}

	dfs(1);

	printf("%lld\n",f[1]);

	return 0;

}

巴特西

CF1146F Leaf Partition 树形DP

最新文章

热门文章