樹形DP

定義

樹形動態規劃（Tree Dynamic Programming，簡稱樹形DP）是一種在樹形結構上應用動態規劃算法的技術。它利用樹的遞歸結構，通過定義狀態和狀態轉移方程，來求解與樹相關的最優化問題，如樹上的最長路徑、最小路徑覆蓋、最大獨立集等。與傳統的線性動態規劃相比，樹形DP更側重于利用樹的子結構特性，遞歸地解決問題，從葉子節點到根節點或反之進行狀態的累積和更新。

運用情況

1. 樹的最長路徑問題：給定一個樹，找出一條路徑，使得該路徑上所有邊的權值之和最大。
2. 數字轉換問題：在不超過 n 的正整數范圍內進行數字變換，求不斷進行數字變換且不出現重復數字的最多變換步數。
3. 樹的中心問題：給定一棵樹，找到一個點，使得該點到樹中其他結點的最遠距離最近。
4. 沒有上司的舞會問題：在一棵以校長為根的樹中，每個職員有一個快樂指數，且沒有職員愿意和直接上司一起參會，求邀請一部分職員參會使得所有參會職員的快樂指數總和最大。
5. 路徑問題：如求解樹中兩個節點間的最大距離、樹的直徑等。
6. 子樹問題：找出具有特定性質的子樹，如最大權獨立集、最小割集等。
7. 計數問題：統計滿足特定條件的子樹數量，如完美子樹的數量、具有特定性質的路徑數量等。
8. 優化問題：在樹上分配資源，使得某個指標最大化或最小化，如最小化涂色成本、最大化收集的資源等。

注意事項

1. 樹形 DP 的 for 循環能優化就優化，比如取?j=min(size(x),m)，k<=min(size(x),m)?之類的，否則很容易 TLE。
2. 要考慮清楚不合法狀態是否會對答案產生影響，如果有就要?memset(dp,-1,sizeof(dp))?和初始化，樹形 DP 中跳過?dp(x)(j)=-1?和?dp(x)(k-j)=-1?之類情況。
3. 狀態定義：正確定義狀態是關鍵，通常包括節點的選擇狀態（是否包含當前節點）和其他與問題相關的附加信息。
4. 狀態轉移：明確狀態之間的依賴關系，設計合理的狀態轉移方程，通常從子節點到父節點進行信息傳遞。
5. 邊界條件：處理好邊界情況，如樹的葉子節點或只有一個節點的子樹。
6. 記憶化搜索：由于樹形DP往往涉及大量的重復計算，使用記憶化搜索可以避免重復計算，提高效率。
7. 遞歸/迭代實現：根據具體情況選擇合適的實現方式，遞歸通常更直觀，迭代則可能在空間復雜度上有優勢。

解題思路

1. 確定狀態表示：需要根據具體問題確定狀態表示，通常是以節點為基本單位，記錄每個節點的相關信息。
2. 定義狀態轉移方程：根據問題的要求，確定狀態之間的轉移關系，即如何從一個狀態轉移到另一個狀態。
3. 確定邊界條件：明確問題的邊界情況，例如根節點的狀態或者葉子節點的狀態。
4. 進行遞歸計算：根據狀態轉移方程，從根節點開始遞歸地計算每個節點的狀態。
5. 求解最優解：根據計算得到的狀態值，求解問題的最優解。
6. 分析問題：首先明確問題的求解目標，識別出問題中的“最優子結構”，即問題的解可以由其子問題的解組合得出。
7. 定義狀態：基于問題特點，定義狀態表示每個節點或子樹在求解過程中的信息，通常包括是否選擇該節點、子樹的某些屬性等。
8. 設計狀態轉移方程：根據問題性質，確定狀態如何從子樹轉移到父節點，即如何通過子節點的信息計算出父節點的信息。
9. 初始化：確定基礎情況，如葉子節點的初始狀態。
10. 實現：使用深度優先搜索（DFS）或廣度優先搜索（BFS）遍歷樹，并根據狀態轉移方程計算每個狀態的值，通常使用記憶化或遞推實現。
11. 回溯獲取答案：根據最終狀態，回溯獲得問題的最優解。

AcWing 323. 戰略游戲

題目描述

活動 - AcWingAcWing 323. 戰略游戲 - AcWing活動 - AcWing

?

?

運行代碼

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2000, M = 4000;
int h[N], e[M], ne[M], idx;
int n;
int f[N][2];
int st[N];
void add(int a, int b)
{e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
void dfs(int u)
{f[u][1] = 1, f[u][0] = 0;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];dfs(j);f[u][0] += f[j][1];f[u][1] += min(f[j][0], f[j][1]);}
}
int main()
{while(scanf("%d", &n) == 1){memset(h, -1, sizeof h);memset(st, 0, sizeof st);idx = 0;for(int i = 0; i < n; i ++ ){int id, cnt;scanf("%d:(%d)", &id, &cnt);while(cnt --){int ver;scanf("%d", &ver);add(id, ver);st[ver] = true;}}int root = 0;while(st[root]) root ++;dfs(root);printf("%d\n", min(f[root][0], f[root][1]));}return 0;
}

代碼思路

1. 數據結構定義:

   • 使用鄰接表表示樹結構，其中h[N]是頭節點數組，e[M]是邊的終點數組，ne[M]是下一個兄弟節點的索引數組，idx用于記錄當前使用的邊的索引。
   • f[N][2]是一個二維狀態數組，其中f[u][0]表示以節點u為根的子樹中選擇不包含該節點的方案數，f[u][1]表示包含該節點的方案數。
   • st[N]標記數組，用來記錄某個節點是否已被其他節點直接連接過，輔助找到樹的根節點。

2. 輸入處理:

   • 讀取整數n表示節點數量。
   • 接收每行輸入，格式為“節點ID:(直接子節點數量) 子節點1 子節點2 ...”，并構建鄰接表表示的樹結構。

3. 尋找根節點:通過遍歷st[]數組找到沒有直接父節點的節點作為樹的根，初始化為0。

4. 深度優先搜索（DFS）:

   • 從根節點開始進行深度優先搜索，遞歸遍歷整棵樹。
   • 對于每個節點u，先假設自己不被選中（f[u][1]=1，表示以自己為根的子樹至少有一種情況是選中自己的），不選中父節點的方案數默認為0（f[u][0]=0）。
   • 遍歷所有子節點，遞歸調用DFS更新f[u][0]和f[u][1]的值。f[u][0] += f[j][1]意味著考慮不選當前節點時，子節點可選擇不包含自己的方案數累加；f[u][1] += min(f[j][0], f[j][1])則是考慮選當前節點時，子節點可以自由選擇是否包含自己，取最小值是因為我們要找的是最小方案數。

5. 輸出結果:最終，輸出根節點的f[root][0]和f[root][1]中的最小值，即為滿足條件的最小方案數。

改進思路

1. 增加注釋：提高代碼的可讀性，特別是對于復雜邏輯的部分，通過注釋說明每段代碼的目的。
2. 變量命名清晰：使變量名更具描述性，便于理解每個變量的用途。
3. 常量分離：將數組大小等硬編碼的常量提取為定義在頂部的常量，便于維護和修改。
4. 函數封裝：將部分功能（如讀取樹的構建）封裝成獨立的函數，提高代碼模塊化。
5. 去除全局變量的過度依賴：盡量減少全局變量的使用，使用函數參數傳遞必要信息。62.