题解：P11529 [THUPC2025 初赛] 辞甲猾扎

· · 题解

稍微转换一下题目，由于所有灰点都不被变成黑色，所以等价于与黑色相邻的点最后都是白色（相邻都被变成后白色黑色就“扩散”不出去了），也就是其要么本身为白色，要么其还和一个白点相邻。

原图是一棵树，考虑树形 dp。稍微分讨一下可以得出一下定义：

设当前有 f_j 向 f_i 转移（j\in son_i），分三种情况：

  1. - $f_{i,0/1/2/3}=+\infty
  2. - $f_{i,1/2/4}=+\infty
  3. - $f_{i,0/4}=+\infty
    • f_{i,1}$ 先对于每个子树求随便染（$w_j=\min(f_{j, 0},f_{j,1},f_{j,3},f_{j,4}$）的方案数和，然后选其中染白代价（$f_{j,3}-w_j$）最小的一个换成 $f_{j,3}

答案即为 \min(f_{rt, 0}, f_{rt, 1}, f_{rt, 3}, f_{rt, 4})。

感觉做得有些复杂了，不过状态定义清楚了就很好做了 （但不好说是谁想状态想了 2h 吃了三发罚时）。所以为什么这题过得比 I 和 D 还多啊。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
const int INF = 1e9;
bool vis[N], f1[N];
int f[N][5];
vector <int> p[N];
void dfs(int k, int fa) {
    f[k][3] = 1; 
    for (auto i : p[k])
        if (i != fa) dfs(i, k);
    if (vis[k]) {
        f[k][0] = f[k][1] = f[k][2] = f[k][3] = INF;
        for (auto i : p[k])
            if (i != fa)
                f[k][4] += min({f[i][1], f[i][3], f[i][4]});
    } else if (!f1[k]) {
        f[k][1] = f[k][2] = f[k][4] = INF; 
        for (auto i : p[k]) {
            if (i == fa) continue;
            f[k][0] += min({f[i][0], f[i][1], f[i][3]});
            f[k][3] += min({f[i][0], f[i][1], f[i][2], f[i][3]}); 
        }
    } else {
        f[k][0] = f[k][4] = INF; int t = INF; 
        for (auto i : p[k]) {
            if (i == fa) continue;
            f[k][2] += min({f[i][0], f[i][1], f[i][4]});
            f[k][3] += min({f[i][0], f[i][1], f[i][2], f[i][3], f[i][4]});
            int w = min({f[i][0], f[i][1], f[i][3], f[i][4]});
            if (!vis[i]) t = min(t, f[i][3] - w); f[k][1] += w; 
        }
        f[k][1] += t; 
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1, x; i <= k; i++) 
        cin >> x, vis[x] = true;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        p[u].push_back(v);
        p[v].push_back(u); 
        f1[u] |= vis[v], f1[v] |= vis[u];
    }
    dfs(1, 0); cout << min({f[1][0], f[1][1], f[1][3], f[1][4]});
    return 0;
}