第一次寫博文，想了半天就拿一道dp/graph的題作為處女作吧
此題有兩種常見解法
（題意比較簡單，就不贅述）
1.二分圖最大匹配
此題等價于問一棵樹中最小點覆蓋數。樹形結構可以把它看做是一個二分圖，一個點集為奇數層，另一個點集為偶數層，顯然滿足二分圖定義，可以套用求二分圖最小點覆
蓋的方法。或者，補全二分圖，根據對稱性，就是前面構造的二分圖的邊數的二倍，故最后結果也要除以二。
2.樹形dp
寫樹形dp時首先要考慮好每個點的可能狀態，這個題中就是選不選這個點。然后就是寫狀態轉移方程
dp[i][0]=sum{dp[j][1]};
dp[i][1]=sum{min(dp[i][0],dp[i][1])};
(j為i的孩子節點集合)
最后答案就是dp[i][0]和dp[i][1]的最小值（i為根節點）
兩種方法樹形dp要快一些，畢竟一棵樹邊很少
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
