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

stu_qiumingxuan · 2025-12-05 15:48:41 · 题解

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

题目传送门

题意

给定一棵树，需要你从树上选取若干个点组成集合，使集合里任意两点之间的距离均大于 2。

求有多少种方案（不含空集，并对 998244353 取模）。

思路

这是一道树形 DP 的题。

一想到 DP 就要开始思考其四要素：

1. 状态：dp_{i,0/1/2} 表示必选点 i 且必选其父节点的子集方案数；不选点 i 但必选其父节点的子集方案数；不选点 i 也不选其父节点的子集方案数。
2. 答案：dp_{1,0}+dp_{1,1}+dp_{1,2}-1（假设点 1 为根），因为其中包含空集，所以减一。
3. 状态转移方程（设 v 是 u 的儿子节点）：
   4. 以上方程同一原理：距离不超过 2 的都是无效方案。
4. 初始状态：dp_{u,0}=1,dp_{u,1}=0,dp_{u,2}=1。

注意：记得取模！！！。

时空复杂度

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

  代码

  
  #include<bits/stdc++.h>
  using namespace std;
  #define ll long long
  #define ull unsigned long long

int const N=3e5+10,MOD=998244353; int n; ll dp[N][3]; vector<int> g[N];

void dfs(int u,int fa){ dp[u][0]=1,dp[u][1]=0,dp[u][2]=1; for(int v:g[u]){ if(v==fa) continue; dfs(v,u); dp[u][0]=dp[u][0]dp[v][2]%MOD; dp[u][1]=(dp[u][1](dp[v][1]+dp[v][2])+dp[u][2]dp[v][0])%MOD; dp[u][2]=dp[u][2](dp[v][1]+dp[v][2])%MOD; } return ; }

void solve(){ cin>>n; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1,1); cout<<(dp[1][0]+dp[1][1]+dp[1][2]-1+MOD)%MOD; return ; }

int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T=1; //cin>>T; while(T--) solve(); return 0; }