The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)

The 15th Chinese Northeast Collegiate Programming Contest C. Vertex Deletion(树形dp)

dp[u][0]=(dp[t][0]+dp[t][2])%mod*dp[u][0]%mod;dp[u][1]=dp[u][1]*dp[t][0]%mod;

const int maxn=1e5+7,inf=0x3f3f3f3f;const ll mod=998244353;const double eps=1e-5;vectorg[maxn];ll dp[maxn][3],n;void dfs(int u,int fa){ dp[u][0]=dp[u][1]=dp[u][2]=1; for(auto t:g[u]){ if(t==fa) continue; dfs(t,u); dp[u][0]=(dp[t][0]+dp[t][2])%mod*dp[u][0]%mod; dp[u][1]=dp[u][1]*dp[t][0]%mod; dp[u][2]=(dp[t][0]+dp[t][2]+dp[t][1])%mod*dp[u][2]%mod; } dp[u][2]=(dp[u][2]-dp[u][1])%mod;}int main(){ int _=read; while(_--){ n=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); ll ans=dp[1][0]+dp[1][2]; ans=(ans+mod)%mod; printf("%d\n",ans); rep(i,1,n) g[i].clear(),dp[i][0]=dp[i][1]=dp[i][2]=0; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。