解析

陰間dp題qwq

不難設計dp：

$$d{p}_{x,0}:x節點沒有被包含、子樹內的方案數$$
$$d{p}_{x,1}:x節點被包含、子樹內的方案數$$

考慮轉移：
dp[x][0]就是兒子的所有方案數(dp[son][0]+dp[son][1])的累乘

dp[x][1]比較麻煩。首先需要乘上當前兒子的方案數，然后還要考慮x節點和當前兒子合并成一個連通塊的情況
合并的時候不能只與一個兒子合并，那樣時非法的，因此我們統計一個到現在為止，至少往上蔓延一個兒子的方案數tot，然后用這個乘新兒子的貢獻，這是本題一個很關鍵的技巧
tot的維護可以使用總方案數tot1-一個兒子都沒有的方案數tot0
（其實這個tot0維護到最后就是dp[x][0]）

考慮如何統計兒子的貢獻
首先兒子被包含時，肯定有一個dp[son][1]要加
但是在兒子沒被包含的時候，我們發現無法統計
于是我們統計一個dp[x][3]，表示在x未被包含時，子樹內可以單向往上生長的方案數
維護也不太難，注意新兒子對dp[x][3]的貢獻還要乘上一個之前的tot0，才能保證是單向的
阿巴阿巴做一做就好了
（更具體的細節建議觀看代碼，還是比較清晰的）

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define il inline #define debug(a,b) fprintf(stderr,a,b) const int N=2e5+100; const int M=3e6+100; const int mod=998244353; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n; int fi[N],cnt; struct node{int to,nxt; }p[N<<1]; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; } ll dp[N][3]; void dfs(int x){if(fi[x]==-1){dp[x][1]=1;return;}ll tot0=1,tot1=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;dfs(to);dp[x][1]=(dp[x][1]*(dp[to][0]+dp[to][1])+(tot1-tot0+mod)%mod*(dp[to][1]+dp[to][2]))%mod;dp[x][2]=(dp[x][2]*(dp[to][0]+dp[to][1])+tot0*(dp[to][2]+dp[to][1]))%mod;tot0=tot0*(dp[to][0]+dp[to][1])%mod;tot1=tot1*(dp[to][0]+dp[to][1]+dp[to][1]+dp[to][2])%mod;}dp[x][0]=tot0;return; } int main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();for(int i=2;i<=n;i++){int x=read();addline(x,i);}dfs(1);printf("%lld\n",(dp[1][0]+dp[1][1])%mod);return 0; }

總結

以上是生活随笔為你收集整理的CF1146F: Leaf Partition（树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。