专栏文章

题解：CF2138C2 Maple and Tree Beauty (Hard Version)

EEngulf
CF2138C2题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minylj7w
此快照首次捕获于
2025/12/02 10:28
3 个月前
此快照最后确认于
2025/12/02 10:28
3 个月前
查看原文
记叶子中深度最小的为 dd，答案不超过 dd。
考虑一种特殊情况，所有的叶子深度相同，均为 dd。这种情况下，所有字符串的长度相等，为了使 LCS 最大，我们希望深度相同的节点（相当于同位置的字符）取同种字符，下文把深度为 ii 的节点称为“第 ii 组”。
记 cic_i 表示深度 ii 的节点个数。如果存在一种选取组的方案 SS 使得 ∑i∈Sci=k\sum\limits_{i\in S} c_i = k，把 00 都放在这些组的节点上，11 放在剩下的节点上，可以使得答案为 dd。可以 0101 背包解决。
如果不存在这样的方案，答案为 d−1d - 1。
证明
现在证明这个东西。
有显然事实：ci≤ci+1c_i \le c_{i + 1}，于是 cdc_d 是最大的（注意这是在所有叶子深度相同的限制下）。考虑这样一种构造方案：我们不要 cdc_d 了，把它拆成 cdc_d 个体积为 11 的物品。这样，只要前 d−1d-1 组存在一种选法使得 ∑i∈Sci=s,k−s≤cd\sum\limits_{i\in S} c_i = s, k-s\le c_d，就可以做到答案 d−1d-1，即 s≥k−cds \ge k - c_d。而 ∑i=1n−1ci=n−cd≥k−cd\sum\limits_{i=1}^{n-1}c_i = n - c_d \ge k - c_d，所以肯定存在。
现在推广到叶子节点的深度不相同。我们猜测，原本按深度分组的方案仍然是最优的。深度 >d> d 的点，不会影响答案，可以随便选，把他们都看作体积为 11 的物品。
证明
深度 <d<d 的组，这样分肯定最优。因为这是每个串的公共前缀。
深度 =d=d 的组，如果深度为 dd 的节点 uu 没有放入该组，那么我们会选择一个 uu 子树内的若干点放入该组。本来可以任选的，现在被强制选则一个值，这是不优的。但如果把 uu 选入，子树内的点就是自由的了，可以随便选了。
相当于做背包的时候，你把一个大体积的物品，拆出若干个 11，不会使答案变劣。
O(n2)\mathcal{O}(n^2)。无法通过本题。
发现我们在做 0101 背包，上 bitset 优化即可做到 O(n2w)\mathcal{O}\left(\dfrac{n^2}{w}\right)，可以通过。
实现CPP
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt;
    while (tt--) {
        int n, k; cin >> n >> k;
        vector<vector<int>> g(n);
        for (int i = 1; i < n; i++) {
            int p; cin >> p; p--;
            g[p].emplace_back(i);
        }

        vector<int> dep(n);
        vector<int> c(n);

        int d = n;

        auto dfs = [&](auto &&self, int u) -> void {
            c[dep[u]]++;
            if (g[u].empty()) d = min(d, dep[u]);
            for (auto v: g[u]) {
                dep[v] = dep[u] + 1;
                self(self, v);
            }
        };

        dfs(dfs, 0);

        d++;
        c.resize(d);
        for (int i = 0; i < n; i++)
            if (dep[i] >= d)
                c.emplace_back(1);

        bitset<200005> f;
        f[0] = 1;
        for (int i = 0; i < c.size(); i++)
            f |= f << c[i];

        cout << d - !f[k] << "\n";
    }
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...