题解：P12621 [ICPC 2025 NAC] Circle of Leaf

Programmeryhl · 2025-08-19 17:17:57 · 题解

题意简介

给定一棵树，在每个叶子节点和根节点之间添加连边，求删除一些边后能形成多少种不同的树。

思路

考虑动态规划，设 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;
}