一.多叉樹變二叉樹。

這個技巧其實也有兩種具體的方法：樹的孩子兄弟表示法與dfs序法。

1.樹的孩子兄弟表示法。

???大家在學習樹形結構時一定接觸了一個多叉樹變二叉樹的方法，就是把每個點與它的第一個兒子連邊，然后將它的兒子依次連接起來。可以結合下面的圖片理解這句話。

總結成口訣就是：第一個兒子是左子樹，其他兒子是左子樹的右子樹（似乎并不押韻，手動滑稽）

2.dfs序法

dfs序就是對一個樹進行一個dfs，然后對于每個點記錄一個時間戳dfn數組，這個時間戳就是這個節點的dfs序，然后我們再記錄一個size數組，表示以每個節點為根的子樹中節點的數量。

假設根節點是u，那么可以容易的推出

第一個兒子的dfs序dfn[first_son]就是dfn[u]+1

第二個兒子的dfs序dfn[second_son]就是dfn[u]+size[first_son]+1

其余同理。

那么u的下一個兄弟的dfs序dfn[next_brother]就是dfn[u]+size[u]+1

這兩個方法大多用于樹形依賴形背包（即使用一個節點必須要使用它所有的祖先），

主要解決點權問題。

主要作用就是可以使決策轉移的過程變成O(1)的了。

最常見的模型就是：有n個物品，有一個m大小的包，每個物品有wi物重與vi物品價值，物品之間存在只有裝了物品a，才能裝物品b的n-1條關系（就是一個樹）。問能取得的最大價值。

簡要分析：顯然是一個多叉樹，考慮轉換。

1.孩子兄弟表示法：對于一個節點i，設dp[i][j]表示在以i為根的子樹中，用大小為j的包能取得的最大價值，那么dp[i][j]=max(dp[left[i]][j-w[i]]+v[i],dp[right[i]][j])

注意，這里的left[i]是i在原樹中的第一個兒子，right[i]是i在原樹中的下一個兄弟。

這個方程是非常好理解的。效率就是O(nm)的。

2.dfs序法：對于一個dfs序為i的節點u，同樣設dp[i][j]表示在以u為根的子樹中，用大小為j的包能取得的最大價值，那么dp[i][j]+v[i]->dp[i+1][j-w[i]]

dp[i][j]->dp[i+size[i]+1][j]

注意，這里的轉移并不是常見的dp[i][j]=max()....（用dp[i][j]的前驅狀態去計算dp[i][j]），而是用dp[i][j]去更新它的后繼狀態。這種方法被稱為刷表法。

兩種方法都是非常巧妙的。但作用也是有限的，只能解決依賴性背包中的點權問題。

二.分組的樹形背包。

這類問題也是有一個常見模型的，具體可參考洛谷P1272重建道路。

下面針對這道題來分析，能夠解決多叉樹的，分組的樹形背包。

此時，我們的兒子與父親之間并不存在依賴型關系，那么我們設dp[k][i][j]表示以i為根的子樹，在前k個兒子中，分離出一個大小為j的子樹（必須包含i），所需要最少的操作次數。

那么我們每計算到第k+1個新的兒子v時(full_son[v]表示v的兒子個數)，

dp[k+1][i][j]=min(dp[k][i][j-t]+dp[full_son[v]][v][t]);

由于一個樹形關系，我們需要在一個dfs上進行dp，即先dfs(v),然后更新dp[k+1][i][j]。

這個k的一維顯然可以用滾動數組優化掉。

那么就是

j=m->1

t=1->j

dp[i][j]=min(dp[i][j-t]+dp[v][t]);

同時，dp一律要注意初始化，即剛開始時所有的dp[i][1]=du[i]（du[i]表示與i連邊的節點數，又稱i的入度（樹是無向邊喲！））

給出參考代碼，方便理解：

?

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int INF=0x3f3f3f3f; const int N=201; struct Edge{int to,next; }e[N*2]; int du[N],a[N],dp[N][N]; int n,k,res=INF,EdgeCnt=0; void addedge(int u,int v){int p=++EdgeCnt;e[p].to=v;e[p].next=a[u];a[u]=p; } void dfs(int u,int fa){dp[u][1]=du[u];for (int p=a[u];p;p=e[p].next){int v=e[p].to;if (v!=fa){dfs(v,u);for (int j=k;j>=1;j--)for (int k=1;k<=j;k++)dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2);}}res=min(res,dp[u][k]); } int main(){scanf("%d%d",&n,&k);memset(dp,0x3f,sizeof(dp));for (int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);du[u]++;du[v]++;}dfs(1,0);printf("%d",res);return 0; }

同樣，這個方法也是有缺陷的，就是無法解決點權問題。大多數運用于邊權問題。點權當然也可以，但是效率較低。

最后總結一句：樹形背包都與dfs離不開關系，所以我們可以在dfs上dp可以寫的更簡單，也可以在dfs預處理后再總刷表法dp。

這三種方法都各有長處，各有短處，實際運用時還是要注意題目本身的。

原博客：https://blog.csdn.net/no1_terminator/article/details/77824790

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的*多叉树的树形背包常见建模方法的全部內容，希望文章能夠幫你解決所遇到的問題。

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