自动搬运

查看原文

来自洛谷，原作者为

	lichenxi111 调整、巩固、充实、提高 | 要知道自己要干什么

搬运于2025-08-24 23:08:07，当前版本为作者最后更新于2025-08-12 17:11:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

没场切的题。

THUPC 2024 对队伍的贡献为 $0$ ！！！

思路

看完题面，可以想到保安站岗这道题，但我们照样设计状态有点问题，对于本题，有一些点是不与黑点相邻的，他们的邻点可以没有白色，注意，是可以，不是一定邻点没有白色。

设计状态：设 $dp_{0/1/2/3}$ 为自己染白/需要儿子染白/需要父亲染白/不需要儿子也不需要父亲染白。

转移方程：

$$dp_{x,0} = dp_{x,0} + \min\{dp_{i,0},dp_{i,1},dp_{i,2},dp_{i,3}\}$$。 自己染白了儿子可以随便选。 $$dp_{x,1} = \min\{dp_{x,1} + \min\{dp_{i,0},dp_{i,1},dp_{i,3}\},dp_{x,3} + dp_{i,0}\}$$。 如果自己还没有儿子染白，那么需要儿子染白，否则儿子只需要不用自己染白，其他随便选。 $$dp_{x,2} = dp_{x,2} + \min\{dp_{i,1},dp_{i,3}\}$$。 只有儿子不需要自己的帮助时，自己可以求助父亲的父亲。如果儿子染白，但自己仍求助父亲，那一定是不优于 $dp_{x,1}$ 的。 $$dp_{x,3} = dp_{x,3} + \min\{dp_{i,0},dp_{i,1},dp_{i,3}\}$$。 只需要儿子不求助自己。 注意，$dp_{x,0/1/2}$ 需要当前节点不为黑，$dp_{x,3}$ 需要对所有节点转移。 如果当前节点为灰点且与黑点相邻，那么他的邻点需要白色，那么 $dp_{x,3} = \inf$。 初始化：如果当前节点为黑，那么 $dp_{x,0/1/2} = \inf$。否则，$dp_{x,0} = 1,dp_{x,1} = \inf$。 ## 代码 ```cpp #include using namespace std; #define int long long int read() { char c; int num = 0,f = 1; c = getchar(); while(c < '0' || '9' < c) { if(c == '-') { f = -1; } c = getchar(); } while('0' <= c && c <= '9') { num = num * 10 + (c - '0'); c = getchar(); } return num * f; } bool f[1000005],ff[1000005]; vector v[1000005]; int dp[1000005][4]; void dfs(int x,int fa) { if(f[x]) { dp[x][0] = 2e9; dp[x][1] = 2e9; dp[x][2] = 2e9; } else { dp[x][0] = 1; dp[x][1] = 2e9; } for(auto i : v[x]) { if(i == fa) { continue; } dfs(i,x); if(!f[x]) { dp[x][0] += min({dp[i][0],dp[i][1],dp[i][2],dp[i][3]}); dp[x][1] = min(dp[x][3] + dp[i][0],dp[x][1] + min({dp[i][0],dp[i][1],dp[i][3]})); dp[x][2] += min({dp[i][1],dp[i][3]}); } dp[x][3] += min({dp[i][0],dp[i][1],dp[i][3]}); } if(!f[x] && ff[x]) { dp[x][3] = 2e9; } } signed main() { int n,k; n = read(),k = read(); for(int i = 1;i <= k;i++) { int x; x = read(); f[x] = 1; } for(int i = 1;i < n;i++) { int x,y; x = read(),y = read(); v[x].push_back(y); v[y].push_back(x); } for(int i = 1;i <= n;i++) { if(f[i]) { for(auto j : v[i]) { ff[j] = 1; } } } dfs(1,0); cout << min({dp[1][0],dp[1][1],dp[1][3]}); return 0; } ```$$