题解归档 - cf2219C

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

• 本地编号：cf2219C
• 本地来源：problems/cf2219C/idea.md
• 题目链接：https://codeforces.com/contest/2219/problem/C
• 原始标题：cf2219C - Coloring a Red Black Tree

思路

cf2219C - Coloring a Red Black Tree

Pattern

Never operate on a red vertex: it can only create new black vertices. Once a
black vertex becomes red, keep it red.

For a state with some black vertices already converted, choosing black vertex
u succeeds with probability:

red_neighbors(u) / degree(u).

The Bellman equation for trying u next is:

E(state) = degree(u) / red_neighbors(u) + E(state + u).

So the optimal strategy is an ordering of the black vertices.

For one black connected component, orient every black-black edge from the
earlier vertex in the ordering to the later vertex. A vertex pays:

degree(u) / (initial_red_neighbors(u) + indeg(u)).

Every orientation of a tree is acyclic, so every orientation corresponds to some
valid order. The problem becomes a tree DP over edge orientations.

DP

Root a black component. For vertex u, dp0[u] is the minimum cost of its
subtree if the parent edge is oriented u -> parent, so it gives no red-neighbor
contribution to u. dp1[u] is the same when the parent edge is oriented
parent -> u, contributing one ready neighbor.

For each child v:

• orient u -> v: child uses dp1[v];
• orient v -> u: child uses dp0[v], and u gets one more ready neighbor.

Sort the deltas dp0[v] - dp1[v]; for each possible number of incoming child
edges, take the cheapest deltas and evaluate the local cost.

Checks

• python tools/math_reasoning_search.py --problem cf2219C -n 5 - required
  precheck done.
• Brute checker uses bitmask DP over all possible next black vertices on small
  random trees.

代码

来源：problems/cf2219C/solution.cpp

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

const double INF = 1e100;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    cout << fixed << setprecision(15);
    while (T--) {
        int n;
        string s;
        cin >> n >> s;
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        vector<int> parent(n + 1, -1), seen(n + 1, 0);
        vector<double> dp0(n + 1, 0), dp1(n + 1, 0);
        double ans = 0.0;

        for (int root = 1; root <= n; root++) {
            if (s[root - 1] == '1' || seen[root]) continue;

            vector<int> order;
            vector<int> st = {root};
            seen[root] = 1;
            parent[root] = 0;
            while (!st.empty()) {
                int u = st.back();
                st.pop_back();
                order.push_back(u);
                for (int v : g[u]) {
                    if (s[v - 1] == '1' || seen[v]) continue;
                    seen[v] = 1;
                    parent[v] = u;
                    st.push_back(v);
                }
            }

            reverse(order.begin(), order.end());
            for (int u : order) {
                int red_neighbors = 0;
                vector<double> delta;
                double base = 0.0;
                for (int v : g[u]) {
                    if (s[v - 1] == '1') {
                        red_neighbors++;
                    } else if (parent[v] == u) {
                        base += dp1[v];
                        delta.push_back(dp0[v] - dp1[v]);
                    }
                }
                sort(delta.begin(), delta.end());

                for (int from_parent = 0; from_parent <= 1; from_parent++) {
                    double best = INF;
                    double cur = base;
                    for (int k = 0; k <= (int)delta.size(); k++) {
                        int ready = red_neighbors + from_parent + k;
                        if (ready > 0) {
                            best = min(best, cur + (double)g[u].size() / ready);
                        }
                        if (k < (int)delta.size()) cur += delta[k];
                    }
                    if (from_parent == 0) dp0[u] = best;
                    else dp1[u] = best;
                }
            }

            ans += dp0[root];
        }

        cout << ans << '\n';
    }
    return 0;
}