樹形Dp入門與例題

樹形dp

顧名思義

在樹上dp

有人就說了

普通的dp都不會還讓我在樹上dp！！

可是

一般的樹形dp沒有别的dp水那麼深

當然了

除了一些毒瘤題之外

樹形dp一般是從下往上

也就是從葉節點到根節點

按這個順序更新資訊

因為葉節點的資訊可以初始化

當然也會有從根節點向葉節點更新的

碰到這種題目再說

樹形dp和遞歸分不開

這就需要掌握dfs的精髓

不大懂的話找個代碼開調試看下它怎麼跑的就好了

我個人一般建無向圖

dfs的時候記錄下前驅就好

有向圖也沒有關系

因為一般是從下往上周遊的

至于樹形背包

樹形背包==分組背包

做題多了見過的模型多了就看得出來了

下面的選課比較經典，入門題

例題

​​Luogu 1352 沒有上司的舞會​​​​HDU 1520 Anniversary party​​ 這兩個是一道題着

隻是下面那個多組資料

題目中還沒說清楚

好坑我

這是最基礎的一類樹形dp

選了父親節點就不能選兒子節點

也就是相鄰的兩個點不能同時選

方程很簡單

為目前節點，為周遊到的節點

第一個方程就是兒子選不選都可以

第二個方程是兒子不能選，因為目前節點已經選了

進階版

​​Luogu 2607 騎士​​​ 這題在上一個方程的基礎上加了點東西

基環樹與删邊

當然主要是拼腦子

具體來這看，挺詳細的了——​​點這裡​​

換換類型

​​Luogu 2014 選課​​​ 每個節點隻有在選了它的父節點之後才能選

題解——​​點這裡​​​​Luogu 2015 二叉蘋果樹​​ 要删去條邊，要使剩下的節點權值最大

題解——​​點這裡​​

​​Luogu 1273 有線電視網​​​ 題面好難說啊自己看去吧( • ̀ω•́ )✧

題解——​​點這裡​​

最小點覆寫問題

每個點能覆寫附近的兩條邊，用最少的點把這張圖覆寫起來

​​​Luogu 2016 戰略遊戲​​​ 诶，

這個好像才是入門的

麻煩不改了

如果目前節點不放置士兵，那麼它的子節點必須全部放置士兵

如果目前節點放置士兵，它的子節點選不選就無所謂了

//目前節點不放

和第一種類型是不是有點像

​​​雙倍經驗​​

​​CF 767C Garland（洛谷）​​​ 給出一顆樹，問能否删除兩條邊使這三部分的點權和相等

題解——​​點這裡​​