题解归档 - cf104077L

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104077L
• 本地来源：problems/cf104077L/idea.md
• 题目链接：https://codeforces.com/gym/104077/problem/L
• 原始标题：L - Tree

思路

L - Tree

For each subtree keep a Pareto frontier (A, C):

A = number of antichain color classes available inside this subtree,
C = minimum number of chain color classes still needed.

For children of the same node:

• antichain classes can be reused across different child subtrees, because different child
  subtrees are pairwise incomparable;
• chain classes cannot be reused across different child subtrees.

So for a fixed A, the forest under a node needs

C_forest(A) = sum child.C(A).

Then add the root:

• put the root into a chain: it can join any existing child chain, so the chain count becomes
  max(1, C_forest(A));
• put the root alone into an antichain class: this uses one extra antichain color and leaves
  C_forest(A) chain colors.

Normalize dominated states after every node. The frontier is small on tested extremal shapes and
the total input size is 1e6.

Checked against exhaustive set-partition brute force for all rooted trees up to 8 nodes.

代码

来源：problems/cf104077L/solution.cpp

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

using pii = pair<int,int>; // (anti colors, chain colors)

static vector<pii> normalize(vector<pii> v) {
    sort(v.begin(), v.end());
    vector<pii> merged;
    for (auto [a, c] : v) {
        if (!merged.empty() && merged.back().first == a) {
            merged.back().second = min(merged.back().second, c);
        } else {
            merged.push_back({a, c});
        }
    }
    vector<pii> res;
    int best = INT_MAX;
    for (auto [a, c] : merged) {
        if (c < best) {
            res.push_back({a, c});
            best = c;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        vector<vector<int>> ch(n + 1);
        ch.reserve(n + 1);
        for (int i = 2; i <= n; i++) {
            int p;
            cin >> p;
            ch[p].push_back(i);
        }

        vector<vector<pii>> dp(n + 1);
        vector<pii> events;
        vector<pii> cand;
        for (int v = n; v >= 1; v--) {
            long long base = 0;
            events.clear();
            for (int u : ch[v]) {
                auto &f = dp[u];
                base += f[0].second;
                for (int i = 1; i < (int)f.size(); i++) {
                    events.push_back({f[i].first, f[i].second - f[i - 1].second});
                }
                vector<pii>().swap(f);
            }
            sort(events.begin(), events.end());

            cand.clear();
            int cur = (int)base;
            auto add_from_forest = [&](int a, int c) {
                cand.push_back({a, max(1, c)}); // put root into a chain
                cand.push_back({a + 1, c});    // put root alone into an antichain color
            };
            add_from_forest(0, cur);
            for (int i = 0; i < (int)events.size();) {
                int a = events[i].first;
                int delta = 0;
                while (i < (int)events.size() && events[i].first == a) {
                    delta += events[i].second;
                    i++;
                }
                cur += delta;
                add_from_forest(a, cur);
            }
            dp[v] = normalize(cand);
        }

        int ans = n;
        for (auto [a, c] : dp[1]) ans = min(ans, a + c);
        cout << ans << '\n';
    }
    return 0;
}