传送门：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的儿子)
然后直接贴代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define enter printf("\n")10 #define space printf(" ")11 typedef long long ll;12 const int INF = 0x3f3f3f3f;13 const int maxn = 5e4 + 5;14 //const int maxm = 1e4 + 5;15 inline ll read()16 {17 ll ans = 0;18 char ch = getchar(), last = ' ';19 while(!isdigit(ch)) {last = ch; ch = getchar();}20 while(isdigit(ch))21 {22 ans = ans * 10 + ch - '0'; ch = getchar(); 23 }24 if(last == '-') ans = -ans;25 return ans;26 }27 inline void write(ll x)28 {29 if(x < 0) x = -x, putchar('-');30 if(x >= 10) write(x / 10);31 putchar('0' + x % 10);32 }33 34 int n, m, c[maxn];35 vector v[maxn];36 bool vis[maxn];37 int dp[maxn][2]; //0:染成黑色，1：染成白色 38 void dfs(int now)39 {40 vis[now] = 1;41 if(now <= n) return;42 dp[now][1] = 1; dp[now][0] = 1;43 for(int i = 0; i < (int)v[now].size(); ++i)44 {45 if(!vis[v[now][i]])46 {47 dfs(v[now][i]);48 dp[now][0] += min(dp[v[now][i]][0] - 1, dp[v[now][i]][1]);49 dp[now][1] += min(dp[v[now][i]][1] - 1, dp[v[now][i]][0]);50 }51 }52 }53 54 int main()55 {56 m = read(), n = read();57 for(int i = 1; i <= n; ++i)58 {59 c[i] = read();60 dp[i][c[i]] = 1; dp[i][c[i] ^ 1] = INF;61 }62 for(int i = 1; i < m; ++i)63 {64 int a = read(), b = read();65 v[a].push_back(b); v[b].push_back(a);66 }67 dfs(n + 1); 68 write(min(dp[n + 1][0], dp[n + 1][1])); enter;69 return 0;70 }
好了，现在讲讲为啥写代码10分钟，debug数小时。
其实就是对于无向图所走边的判重问题。
众所周知，用一个vis数组就能解决，然后因人而异在dfs开头标记或是在if(!vis[i]) 后 vis[j] = 1 (j为i的孩子).
然后我就是第二种写法。
然而
这会错
因为
根节点
没有
打！上！标！记！
所以，请务必vis[n + 1] = 1后，在dfs(n + 1)…………