<style> .reveal .slides { text-align: left; font-size:28px; } </style> # DP 不難的DP 2/17 ---- * 樹DP * 樹背包 --- ## 樹DP 使用了樹的遍歷模式，通常以遞迴進行解題。 ---- [例題 沒有上司的舞會](https://www.luogu.com.cn/problem/P1352) 題目敘述 : 給你一棵樹，每個節點有權值，選擇最多節點使總和最大，限制為若選擇了一個節點，則不能選擇他的父節點(也就是不能選擇子節點)。 我再說一次 先看經典題 先理解他的做法。 $dp[i][j]$ 表示以 $i$ 為根時子樹的最優解 $j$ 為 $0/1$ 表 $i$ 不選擇或是 $i$ 被選擇，以及再 dfs 返回上一層的時候更新答案。 ---- 對於每個狀態，都存在兩種決策： 1. 不選擇父節點 $i$ 時，子節點 $x$ 可以選擇，也可以不選擇，此時有 $f(i,0) = \sum\max\{f(x,1),f(x,0)\}；$ 2. 選擇父節點 $i$ 時，子節點 $x$ 絕對不能選，此時有 $f(i,1) = \sum{f(x,0)} + a_i$。 ---- 看code ```cpp void calc(int k) { vis[k] = 1; for (int now : edge[k]) { // 枚舉該節點的每個子節點 if (vis[now]) continue; calc(now); f[k][1] += f[now][0]; f[k][0] += max(f[now][0], f[now][1]); // 轉移方程 } return; } int main() { cin>>n; for (int i = 1; i <= n; i++) cin>>f[i][1]; for (int i = 1; i < n; i++){ cin>>l>>k; is_root[l] = 1; //紀錄根 edge[l].push_back(k); } for (int i = 1; i <= n; i++) if (!is_root[i]) { // 從root開始DFS calc(i); cout<<max(f[i][1], f[i][0])<<"\n"; return 0; } } ``` ----  一棵樹，根據樹DP的規劃，會先遞迴到最底層也就是7 / 6 / 4 會優先納入考量 然後就可以畫出遞迴圖 ---- ## 例題(作業A) 題意 : 一顆二元樹 根被感染了，每一次操作都會擴散，每次操作可以移除一個點，求最多可以拯救幾個點(被移除的點不再此限)。 要先預處理每個節點的子樹數量，這個大家應該都會 然後就可以很簡單的求出轉移式 $dp[i] = max(dp[i],dp[j]+sum[i]-sum[j]-2)$ ---- 樹DP都是從底往上做的，所以要先從小case去想，會很像是分治的想法，但其實最後的組合會變得很簡單，完全不抽象。 ---- ## 例題2 作業2 題意 : 給你一棵樹，你可以任意刪除度數<=1的點，操作完之後進行壓縮，把所有度數=2的點刪掉，然後把被刪除點兩側的點連接起來。 詢問最後的樹最大的數字總和為多少。 ---- 其中要先認知到一點，由於壓縮的操作，所以會有以下情況 ## 鍊子中間完全不算 鏈子會只有兩端才加進最後的答案裡面，但由於可以刪除度數為一的，因此其實最外面的點是誰是可以決定的。 ---- 於是我們的 $dp$ 會有 $dp[i]=value[i]$ 刪到把 $i$ 變成鍊的邊邊 $dp[i]= max(dp[j])$ 所有子節點裡面最大，因為 $i$ 本身是中間的點，不是邊邊，因此只能直接抓子節點的value *j是所有的子節點 ---- 而其中轉移式裡面的 $max(dp[j])$ 也可以替換成 $value[i]+dp[j]$ 一旦度數超過1 ，則點2也不會被壓縮刪除，所以要加上自己的跟所有的子樹分支 ---- 所以這題特別判一下度數，就可以簡單的過，不過有些細節要注意，可能會不小心被壓縮，注意負數 ---- ## 2019ICPC B 樹DP 題意 : 給你一棵樹，全白，請你染黑，根據以下規則。 每次染黑會把選擇的點，選擇的點連接的邊，選擇的點連接的點，全部染黑 1. 若邊上兩邊的點都是黑的，則此邊自動染黑。 2. 若某點度數 >1 且 $k-1$ 條邊都已經染黑，則剩下那條邊以及連接的點自動染黑。 詢問最少需要做幾次操作可以把整棵樹染黑(包含點和邊)。 ----  a 為成功全部染黑的例子 b 則錯誤 ---- 此題難點在於多出來的規則，會讓你原本很簡單的 $dp[n][0/1]$ 變成需要特判，很難的規則。 那具體上需要怎麼做，也就是需要多開一個維度 $dp[i][j\ \ 2/1/0 ][k\ \ 1/0 ]$ i 為第幾個點 j 為 被子節點染黑/直接染黑/被父節點染黑 k 為 是否可以利用規則2多染黑一個點，一個邊 ---- 為什麼不需要轉移白點呢? 因為你要全部染黑，所以不會有白點。 ---- 這題 根本做不出來 :BREAD: SLW 會需要分成父節點染色的還是子節點染色的是為了判出第三個象限的 0/1 而先討論較複雜的第三象限的部分。 $dp[u][0][1]=dp[u][0][0]$ --- ## 樹背包 ---- 先看一下之前的上課例題。 [例題 選課](https://www.luogu.com.cn/problem/P2014) 題目敘述 : 現在有 $n$ 門課程，第 $i$ 門課程的學分為 $a_i$，每門課程有零門或一門先修課，有先修課的課程需要先學完其先修課，才能學習該課程。 一位學生要學習 $m$ 門課程，求其能獲得的最多學分數。 可以想像成先修課就是那門課的父節點，於是你就會發現它給的一張圖就是一張森林，那我們要做的第一件事情就是創造一個 ${0,0}$ 的node，而其是指向所有樹上的根節點，讓這個森林形成一棵樹。 ----  ---- 所以它變成了，可以選擇 $m+1$ 個點的樹上問題，詢問選擇 $m+1$ 個點後的最大值。 有了一棵樹之後，很重要的想法是，樹DP是從底往上，樹背包也是。 他只是變成了 有先例條件的DP，0/1選擇問題。 ---- 於是就可以假設 $f(x,i,j)$ 表示以節點 $x$ 為根的子樹中，已經遍歷了節點 $x$ 的前 $i$ 棵子樹，選了 $j$ 門課程的最大學分。 那我們只需要枚舉 $x$ 的每個子節點 $y$ ，然後枚舉每個 $y$ 選擇課程的方案，再返回到 $x$ 那層，使用到背包的想法去做樹上的dp，可以得出以下轉移方程 : $f(x,i,j)=\max_{k \leq j,k \leq \textit{siz_y}} f(y,i-1,j-k)+f(y,s_y,k)$ ```txt s_y y的子節點數量 siz_y 以y為根的子樹大小 須注意的是選擇的課程數量 j 不能 > m ``` 那這時候我們的 $dp[x][i][j]$ 會發現可以把 $[i]$ 維壓掉(滾動數組)，所以會剩下 $dp[x][j]$ ，意義為 $x$ 為根的子樹選擇了 $j$ 堂課的最大學分。 所以 $dp[0][m+1]$ 就是答案，因為你會算是需要多選 $0$ 那堂課，因此需要額外加 $1$ 。 ---- 所以很輕鬆的code就出來了 ```cpp int dfs(int u) { int p = 1; //已選課堂數 dp[u][1] = s[u]; for (int v : edge[u]) { int siz = dfs(v); for (int i = min(p, m + 1); i; i--) //不倒序的話會重複選取 for (int j = 1; j <= siz && i + j <= m + 1; j++) dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]); //去掉一維後的轉移式 p += siz; } return p; } ``` ---- 相信大家都會上面那種很無聊的樹DP，所以我們來看這種 ## 例子2 作業 題意 : $n$ 個點的樹 求最少切斷幾條邊可以變成剛剛好 $m$ 個點的樹。 ---- 那會有很直觀的第一個想法，如果第 $i$ 點的子樹大小剛好等於 $n-m$ 則你只需要剪斷這條邊即可。 那再來會發現，好像有點難實作了，如果並沒有剛好的怎麼辦呢? ---- 定義 $dp[i][j]$ 以 $i$ 為根節點，求只剩下 $j$ 個點的時候，最少切斷要幾個邊 那很明顯，不管 $i$ 是多少，$dp[i][1]$ 就等於 $i$ 的子樹大小 (把所有子節點全部切斷) 那如果是 $dp[i][2]$ 呢? 他就會是 min($dp[i][1]$ + $dp[子節點][1] - 1$) 那如果是 $dp[i][3]$ 呢? 他就會是 min($dp[i][1]$ + $dp[子節點][2] - 1$) 或 min($dp[i][2]$ + $dp[子節點][1] - 1$) 那結論就明顯出來的。 ---- 樹上背包很多時候都要考慮，根節點自己留了多少，子節點對你貢獻了多少，常常會是一個獨立的迴圈。 常常有連邊的話就會是樹上問題，有先後順序就很容易變成DP，其實兩個部分是可以分開來想的。 ---- ## 連結: https://vjudge.net/contest/608693