P12621 [ICPC 2025 NAC] Circle of Leaf
题意简介
给定一棵树，在每个叶子节点和根节点之间添加连边，求删除一些边后能形成多少种不同的树。
思路
考虑动态规划，设 \(dp_{i,1/0}\) 表示在以 \(i\) 为根的子树中是/否使用“叶子”边的方案数。
对于 \(u \rightarrow v\)，自下而上地更新 \(dp\) 值，可分为两种情况：
-
若不删去 \(u \rightarrow v\) 这条边，\(dp_{u,0}\) 仅有一种贡献来源即 \(dp_{u,0}=dp_{u,0} \times dp_{v,0}\)，而 \(dp_{u,1}\) 有两种选择，分别是将“叶子”边接在 \(u\) 的别的孩子上或接在 \(v\) 的子树上，也就是 \(dp_{u,1}=dp_{u,1} \times dp_{v,0} + dp_{u,0} \times dp_{v,1}\)。
-
若删去 \(u \rightarrow v\) 这条边，则 \(dp_{u,0}=dp_{u,0} \times dp_{v,1}\)，此时 \(u\) 的别的孩子与 \(v\) 的子树上均可以接“叶子”边，有 \(dp_{u,1}=dp_{u,1} \times dp_{v,1}\)。
时间复杂度显然 \(O(n)\)。
Code
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=2e5+5;
const int MOD=998244353;
int n,head[N],nxt[N<<1],to[N<<1],cnt=0;
long long dp[N][2];
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
void dfs(int u,int father)
{if(father) dp[u][0]=1;int son=0;for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v==father) continue;son++;dfs(v,u);dp[u][1]=(dp[u][1]*dp[v][0]%MOD+dp[u][0]*dp[v][1]%MOD+dp[u][1]*dp[v][1]%MOD)%MOD;dp[u][0]=(dp[u][0]*dp[v][0]%MOD+dp[u][0]*dp[v][1]%MOD)%MOD;}if(!son) dp[u][0]=dp[u][1]=1;
}
int main()
{IOS;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;add(u,v),add(v,u);}dp[1][1]=1;dfs(1,0);cout<<max(dp[1][1],dp[1][0])<<'\n';return 0;
}
完结撒花～