傳送門：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("\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<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)…………

轉載于:https://www.cnblogs.com/mrclr/p/9339989.html

總結

以上是生活随笔為你收集整理的[CQOI2009]叶子的染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。