传送门：https://www.luogu.org/problemnew/show/P3155
一道挺水的树形dp题，然后我因为一个挺智障的问题debug了一晚上……
嗯……首先想，如果一个点的颜色和他的儿子相同，那么删去他儿子的颜色显然不影响，而且更符合最优解，然后我们dp时就从子树开始往上找，将儿子的状态转移给父亲时，就将儿子的颜色删去。
所以开一个dp[maxn][2]，
dp[i][0]表示节点i染成黑色，以i为根的子树最少需要染色的点数。
dp[i][1]节点i染成白色，以i为根的子树最少需要染色的点数。
所以
dp[i][0] = 1+∑min(dp[j][0] - 1, dp[j][1]) (j取遍i的儿子)
dp[i][1] = 1+∑min(dp[i][0], dp[i][1] - 1) (j取遍i的儿子)
然后直接贴代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
using namespace std;
#define enter printf("\n")
#define space printf(" ")
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 5e4 + ;
//const int maxm = 1e4 + 5;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar('' + x % );
} int n, m, c[maxn];
vector<int> v[maxn];
bool vis[maxn];
int dp[maxn][]; //0:染成黑色，1：染成白色
void dfs(int now)
{
vis[now] = ;
if(now <= n) return;
dp[now][] = ; dp[now][] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
if(!vis[v[now][i]])
{
dfs(v[now][i]);
dp[now][] += min(dp[v[now][i]][] - , dp[v[now][i]][]);
dp[now][] += min(dp[v[now][i]][] - , dp[v[now][i]][]);
}
}
} int main()
{
m = read(), n = read();
for(int i = ; i <= n; ++i)
{
c[i] = read();
dp[i][c[i]] = ; dp[i][c[i] ^ ] = INF;
}
for(int i = ; i < m; ++i)
{
int a = read(), b = read();
v[a].push_back(b); v[b].push_back(a);
}
dfs(n + );
write(min(dp[n + ][], dp[n + ][])); enter;
return ;
}
好了，现在讲讲为啥写代码10分钟，debug数小时。
其实就是对于无向图所走边的判重问题。
众所周知，用一个vis数组就能解决，然后因人而异在dfs开头标记或是在if(!vis[i]) 后 vis[j] = 1 (j为i的孩子).
然后我就是第二种写法。
然而
这会错
因为
根节点
没有
打！上！标！记！
所以，请务必vis[n + 1] = 1后，在dfs(n + 1)…………