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

给一个状态设计极简的题解：

记

f_{i,0/1}

表示

i

选或者不选，子树内的方案数。

f_{i,1}

的值是对于所有孙子做乘积：

\prod_{j \in \text{grandson}(i)} f_{j,0}

。所有儿子默认不选。显然是对的。

这个时间复杂度也是对的，因为每个点只有一个爷爷，所以这一步统计总共是

\mathcal O(n)

的。

对于

f_{i,0}

，儿子可选可不选。但是，因为兄弟之间的距离为 2，所以至多选一个儿子。

那就用经典技巧：维护

f_{\text{son},0}

的前缀积和后缀积，如果选取第

k

个儿子，就把

f_{k,1}

和

k-1

前缀、

k+1

后缀拼起来。

也可以用逆元处理，但是参考 ICPC 成都，说不定树状 DP 卡零逆元呢。

代码如下：

CPP

#include <bits/stdc++.h>
using namespace std;

const int MAXN(3e5 + 5);
const long long MOD(998244353);

int n;
vector<int> tree[MAXN];

long long dp[MAXN][2];
long long ll[MAXN], rr[MAXN];

void dfs(int u, int f) {
    dp[u][1] = 1;
    int cnt = 0;
    
    for (int v : tree[u]) {
        if (v == f) continue;
        dfs(v, u);
    }
    
    for (int v : tree[u]) {
        if (v == f) continue;
        for (int w : tree[v]) {
            if (w == u) continue;
            (dp[u][1] *= dp[w][0]) %= MOD;
        }
    }
    
    for (int v : tree[u]) {
        if (v == f) continue;
        cnt++;
        ll[cnt] = rr[cnt] = dp[v][0];
    }
    ll[0] = rr[cnt + 1] = 1;
    for (int i = 1; i <= cnt; i++) {
        ll[i] = (ll[i - 1] * ll[i]) % MOD;
    }
    for (int i = cnt; i >= 1; i--) {
        rr[i] = (rr[i + 1] * rr[i]) % MOD;
    }
    dp[u][0] = ll[cnt];
    int id = 0;
    for (int v : tree[u]) {
        if (v == f) continue;
        id++;
        (dp[u][0] += (dp[v][1] * ll[id - 1] % MOD * rr[id + 1]) % MOD) %= MOD;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1, 0);
    cout << (dp[1][0] + dp[1][1] + MOD - 1) % MOD << endl;
    return 0;
}

另：我考完用 Copilot 辅助复现了我的代码，结果神人 Copilot 不会写后缀积，写了这么依托：

CPP

rr[i] = rr[i + 1] * ll[i] % MOD;

挂的只剩 30 分。吓我一跳。现在开始后怕，感觉考场上可能会挂一些莫名其妙的分。

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

文章操作

相关推荐

评论

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