题解：P12844 [蓝桥杯 2025 国 A] 树

· · 题解

题解：P12844 [蓝桥杯 2025 国 A] 树

考虑树形 DP。dp_{i} 表示以 i 为根节点的子树中最多选的数量。

不想截图了，就凑合着看字符画吧。

如果根节点不选，就选成这样（o 表示不选，x 表示可以选也可以不选，.................. 表示以下都不考虑）

        o
       /|\
      x o o
     / / \ \
    o x   o x
..................

        o
       /|\
      x o o
     / / \ \
    o o   x x
..................
        o
       /|\
      o x o
     / / \ \
    x o   o x
..................

        o
       /|\
      o o x
     / / \ \
    x x   o o
..................

        o
       /|\
      o o x
     / / \ \
    x o   x o
..................

可以看到，子节点至多选一个；不选的子节点的子节点也最多选一个；选的子节点就是其子树的根节点选上的结果。

如果根节点选，那么长这样：

        x
       /|\
      o o o
     / / \ \
    o o   o o
..................

根节点选了，子节点及其子节点都不能选。

那么重新定义状态：

然后就有转移方程：

dp_{u,0}\gets\prod_{v\in son_u}dp_{v,2}\\ dp_{u,1}\gets\sum_{v\in son_u}\frac{\prod_{w\in son_u}(dp_{w,1}+dp_{w,2})}{dp_{v,1}+dp_{v,2}}\cdot dp_{v,0}\\ dp_{u,2}\gets\prod_{w\in son_u}(dp_{w,1}+dp_{w,2})

除法用逆元维护。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int maxn=3e5+5;
vector<int>G[maxn];
ll dp[maxn][3];// 0为自己选；剩下为自己不选：1为下面有一个选的；2为下面都不选
ll n;
const int MOD=998244353;
int qpow(ll x,int y=MOD-2){
    ll ans=1;
    while(y){
        if(y&1)ans*=x,ans%=MOD;
        x*=x;
        x%=MOD;
        y>>=1;
    }
    return ans;
}
void dfs(int u,int fa){
    dp[u][0]=1;
    dp[u][1]=0;
    dp[u][2]=1;
    for(auto v:G[u]){
        if(v==fa)continue;
        dfs(v,u);
        dp[u][2]=dp[u][2]*(dp[v][1]+dp[v][2])%MOD;
        dp[u][0]=dp[u][0]*dp[v][2]%MOD;
    }
    for(auto v:G[u]){
        if(v==fa)continue;
        dp[u][1]+=dp[u][2]*qpow(dp[v][1]+dp[v][2])%MOD*dp[v][0]%MOD;
        dp[u][1]%=MOD;
    }
}
signed main(){
    cin>>n;
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    cout<<((dp[1][0]+dp[1][1]+dp[1][2]-1)%MOD+MOD)%MOD<<"\n";
    return 0;
}