P11529 [THUPC 2025 初赛] 辞甲猾扎
lichenxi111
·
·
题解
前言
没场切的题。
THUPC 2024 对队伍的贡献为 0 ！！！
思路
看完题面，可以想到保安站岗这道题，但我们照样设计状态有点问题，对于本题，有一些点是不与黑点相邻的，他们的邻点可以没有白色，注意，是可以，不是一定邻点没有白色。
设计状态：设 dp_{0/1/2/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<bits/stdc++.h>
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<int> 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;
}
```