传送门：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 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<cctype> 7 #include<vector> 8 using namespace std; 9 #define enter printf(" ") 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<int> 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)…………