题解：CF1929E Sasha and the Happy Tree Cutting

xiaoyi_zeng · 2026-02-03 11:44:19 · 题解

CF1929E

前言

题目传送门 1

题目传送门 2

还是不错的题目。

思路

注意到 \sum 2^k \leq 2^{20}，考虑状压。

不过在这之前，你需要先想想怎么通过点存储边，不难发现一个节点 u 可以有多个儿子，而一个节点 v 只有一个父亲节点 fa_v。

不妨用 v 来表示一条 u \rightarrow v (fa_v=u) 的路径，将这条路径命名为边 u。

对于每条边 u，存储一个 chs_u 表示包含这条边的路径的集合（用状压）。

然后一个显然的 dp，令 f_S 表示，已经满足的路径集合为 S 的方案数。

则有：f_S = \min\limits_{S' | chs_u = S} f_S'+1，用刷表法即可做到 O(n2^k)。

现在我们面临着两个问题，一是怎么算出 chs_u，二是怎么优化 O(n2^k) 的时间复杂度。

对于第一个问题，考虑树上差分。此时有三种情况：（设当前限制为第 i 个，状压过后的值是 k=2^i）

综上所述，只需要让 chs_u \leftarrow chs_u \oplus k, chs_v \leftarrow chs_v \oplus k。

对于第二个问题，注意到相同的 chs 贡献示一样的，而不同的 chs 的个数是 O(k) 的，于是就优化到了 O(k2^k)。

代码

Talk is cheap, give me your code.

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

const int N = 1e5 + 5, M = (1 << 20) + 5;

int n, k;
vector <int> g[N];
int pre[N], dp[M];

void dfs(int f, int u){
    for (auto v : g[u]) if (v != f) dfs(u, v);
}

void calc(int f, int u){
    for (auto v : g[u]) if (v != f) calc(u, v), pre[u] ^= pre[v];
}

void please_ac(){
    cin >> n;
    for (int i = 1; i <= n; i ++ ) g[i].clear(), pre[i] = 0;
    for (int i = 1; i < n; i ++ ){
        int u, v; cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(0, 1);

    int k; cin >> k;
    for (int i = 0; i < k; i ++ ){
        int u, v; cin >> u >> v; pre[u] ^= (1 << i), pre[v] ^= (1 << i);
    }
    calc(0, 1);

    set <int> s; vector <int> v;
    for (int i = 2; i <= n; i ++ ) if (!s.count(pre[i])) s.insert(pre[i]), v.push_back(pre[i]);

    for (int i = 1; i < (1 << k); i ++ ) dp[i] = 0x3f3f3f3f;
    for (int i = 0; i < (1 << k); i ++ )
        for (auto j : v) dp[i | j] = min(dp[i | j], dp[i] + 1);
    cout << dp[(1 << k) - 1] << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T_T = 1; cin >> T_T;
    while (T_T -- ) please_ac();
}

后记

求赞 qwq，你的赞和评论对我有很大的帮助！