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

题意

给定一棵树，现要求在树上选若干个点（不能不选），使得任意两点间的距离严格大于 2，求选择方案数。

思路

这题肯定是上位绿了。

考虑树上 dp。题目要求距离严格大于 2，那么也就是距离最小的两个点距离大于 2。考虑 LCA 不为其中之一的两点 ，如果需要从以 为根的子树中选点，那么只需求 间的距离即可。如果这个距离等于 2，那么 至少有一个不能选，如果大于 2，那么全部可选。

设计状态 表示以 为根的子树内，从 出发，走 步，从 开始的前 个点均不选的方案数。发现， 的状态都可以扔进 里面。所以重新设计状态 表示以 为根的子树内，从 出发，走 步，从 开始的前 个点均不选的方案数。
考虑转移：

• 表示从 出发走 步，从 开始的前 个都不选的方案数，也即选择 的方案数，那么 应当从 转移而来， 为 的子节点。那么有

• 表示从 出发走 步，从 开始的前 个都不选的方案数，也即从以子节点为根的子树中选取节点的方案数。此时，因为距离严格大于 2，所以最多有一个子节点出现。又发现，不选子节点的方案数被 包含，所以只需计算有一个子节点出现的答案即可。有

• 表示从 出发走 步，从 开始的前 个都不选的方案数，也即不选 和其任何子节点。那么 应当从 转移而来。有

转移时，可以先计算 ，在计算 时，利用 的答案乘上 即可。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 3e5 + 10, MOD = 998244353;

int n;
ll dp[MAXN][3], pre[MAXN];
ll fac[MAXN], inv[MAXN];
vector<int> g[MAXN];

ll qpow(ll x, ll y) {
  ll res = 1;
  for (; y; y >>= 1, (x *= x) %= MOD) {
    if (y & 1) (res *= x) %= MOD;
  }
  return res;
}

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

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  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;
  return 0;
}