樹形DP --算法競賽專題解析（17）

本系列文章将于2021年整理出版，書名《算法競賽專題解析》。

前驅教材：《算法競賽入門到進階》 清華大學出版社

網購：京東 當當      想要一本作者簽名書？點我

如有建議，請加QQ 群：567554289，或聯系作者QQ：15512356

暑假福利：公衆号免費連載作者以前寫的書《胡說三國》

文章目錄

• 1、樹形DP的基本操作
• 2、背包與樹形DP
• 3、應用示例：樹的重心
• 4、樹形DP習題

   在樹這種資料結構上做DP是常見的題型：給出一棵樹，要求實作最少的代價（或最大收益）。

   在樹上做動态規劃顯得非常自然，因為樹本身有“子結構”性質（樹和子樹），具有遞歸性，符合本書“DP的兩種程式設計方法”這一節中所提到的“記憶化遞歸”的思路，是以樹形DP一般就這樣程式設計。

   基于樹的解題步驟一般是：先把樹轉為有根樹（如果是幾個互不連通的樹，就加一個虛拟根，它連接配接所有孤立的樹），然後在樹上做DFS，遞歸到最底層的葉子節點，再一層層傳回資訊更新至根結點。顯然，樹上的DP所操作的就是這一層層傳回的資訊。不同的題目需要靈活設計不同的DP狀态和轉移方程。

1、樹形DP的基本操作

   先看一個簡單的入門題。通過這一題，了解樹的存儲，以及如何在樹上設計DP和進行狀态轉移。請讀者特别注意DP設計時的兩種處理方法：二叉樹、多叉樹。

二叉蘋果樹 洛谷P2015 https://www.luogu.com.cn/problem/P2015

題目描述：有一棵蘋果樹，如果樹枝有分叉，一定是分2叉。這棵樹共有n個結點，編号為1~n，樹根編号是1。用一根樹枝兩端連接配接的結點的編号來描述一根樹枝的位置，下面是一棵有4個樹枝的樹：

2 5

\ /

3 4

\ /

1

   這棵樹的枝條太多了，需要剪枝。但是一些樹枝上長有蘋果，最好别剪。給定需要保留的樹枝數量，求出最多能留住多少蘋果。

輸入格式：第1行2個數，n和q(1 ≤ Q ≤N, 1 < N ≤ 100)。n表示樹的結點數，q表示要保留的樹枝數量。接下來n - 1行描述樹枝的資訊。每行3個整數，前兩個是它連接配接的結點的編号。第3個數是這根樹枝上蘋果的數量。每根樹枝上的蘋果不超過30000個。

輸出格式：一個數，最多能留住的蘋果的數量。

輸入樣例：

5 2

1 3 1

1 4 10

2 3 20

3 5 20

輸出樣例：

21

  首先是樹的存儲，在計算之前需要先存儲這棵樹。樹是圖的一種特殊情況，樹的存儲和圖的存儲差不多：一種方法是鄰接表，用vector實作又簡單又快；另一種方法是鍊式前向星1，對空間要求很高時可以使用，編碼也不算複雜。本題給出的代碼用vector存樹，後面的例題poj 3107用鍊式前向星存樹。

  這一題的求解可以從根開始自頂向下，是典型的DP思路。

  定義狀态dp[u][j]，它表示以結點u為根的子樹上留j條邊時的最多蘋果數量。dp[1][q]就是答案。

  狀态轉移方程如何設計？下面給出2種思路，二叉樹方法、多叉樹（一般性）方法。

  （1）二叉樹

  本題是一棵二叉樹，根據二叉樹的特征，考慮u的左右子樹，如果左兒子lson留k條邊，右兒子rson就留j - k條邊，用k在[0, j]内周遊不同的分割。讀者可以嘗試用這種思路寫出“記憶化搜尋”的代碼，其主要步驟參考下面的僞代碼：

int dfs(int u, int j){      //以u為根的子樹，保留j個樹枝時的最多蘋果
    if(dp[u]][j] >=0)       //記憶化，如果已計算過，就傳回
       return dp[u][j];
    for(int k=0; k<j; k++)   //用k周遊
       dp[u][j] = max(dp[u][j], dfs(u.lson,k) + dfs(u.rson, j-k)); //左右兒子合起來
    return dp[u][j];
}
           

  二叉樹的DP設計非常簡潔易懂。如果題目是多叉樹，可以先轉為二叉樹，然後再設計DP；不過一般沒有必要這樣做。

  （2）多叉樹

  本節不準備用上面的方法，因為它局限于二叉樹這種結構。下面用多叉樹實作，這是一般性的方法。把狀态轉移方程寫成以下的形式：

for(int j = sum[u]; j >= 0; j--)           //sum[u]是u為根的子樹上的總邊數
	for(int k = 0; k <= j - 1; k++)        //用k周遊不同的分割
        dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w); //狀态轉移方程
           

  其中v是u的一個子結點。dp[u][j]的計算分為2部分：

  1）dp[v][k]：在v上留k個邊；

  2）dp[u][j-k-1]：除了v上的k個邊，以及邊[u,v]，那麼以u為根的這棵樹上還有j-k-1個邊，它們在u的其他子結點上。

洛谷P2015的代碼（鄰接表存樹）

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200;
struct node{
 	int v, w;                   //v是子結點，w是邊[u,v]的值
 	node(int v = 0, int w = 0) : v(v), w(w) {}
};
vector<node> edge[MAXN];
int dp[MAXN][MAXN], sum[MAXN];  //sum[i]記錄以點i為根的子樹的總邊數
int n, q;
void dfs(int u, int father){
	for(int i = 0; i < edge[u].size(); i++) {  //用i周遊u的所有子節點
        int v = edge[u][i].v, w =  edge[u][i].w;
        if(v == father) continue;              //不回頭搜父親，避免循環
        dfs(v, u);                             //遞歸到最深的葉子結點，然後傳回
        sum[u] += sum[v] + 1;                  //子樹上的總邊數
      //for(int j = sum[u]; j >= 0; j--)         
      //    for(int k = 0; k <= j - 1; k++)    //兩個for優化為下面的代碼。不優化也行
        for(int j = min(q, sum[u]); j >= 0; j--)   
        	for(int k = 0; k <= min(sum[v], j - 1); k++)
                dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w);
    }
}
int main(){
    scanf("%d%d", &n, &q);            //n個點，留q條樹枝
	for(int i = 1; i < n; i++){
        int u, v, w;  scanf("%d%d%d", &u, &v, &w);
        edge[u].push_back(node(v,w)); //把邊[u,v]存到u的鄰接表中
        edge[v].push_back(node(u,w)); //無向邊
    }    
    dfs(1, 0);                        //從根結點開始做記憶化搜尋
    printf("%d\n", dp[1][q]);    
    return 0;
}
           

  二叉樹和多叉樹的讨論。本題是二叉樹，但是上面的代碼是按多叉樹處理的。代碼中用v周遊了u的所有子樹，并未限定是二叉樹。狀态方程計算dp[u][j]時包含兩部分dp[u][j-k-1]和dp[v][k]，其中dp[v][k]是u的一個子樹v，dp[u][j-k-1]是u的其他所有子樹。

  上面代碼中最關鍵的是dfs()函數中j的循環方向，它應該從sum[u]開始遞減，而不是從0開始遞增。例如計算dp[u][5]，它用到了dp[u][4]、dp[u][3]等等，它們可能是有值的，原值等于以前用u的另一個子樹計算得到的結果，也就是排除目前的v這個子樹時計算的結果。

  1）讓j遞減循環，是正确的。例如先計算j = 5，dp[u][5]用到了dp[u][4]、dp[u][3]等，它們都是正确的原值；下一步計算j = 4時，新的dp[u][4]會覆寫原值，但是不會影響到對dp[u][5]的計算。

  2）讓j遞增循環，是錯誤的。例如先計算j = 4，得到新的dp[u][4]；再計算dp[u][5]，這時候需要用到dp[u][4]，而此時的dp[u][4]已經不再是正确的原值了。

  讀者可以聯想“滾動數組”這一節的“自我滾動”的編碼，它的循環也是從大到小遞減的。兩者的原理一樣，即新值覆寫原值的問題。

  k的循環順序則無所謂，它是[0, j - 1]區間的分割，從0開始遞增或從j - 1開始遞減都行。

  兩個for循環還可以做一些小優化，詳情見代碼。

  複雜度：dfs()遞歸到每個結點，每個結點有2個for循環，總複雜度小于 O ( n 3 ) O(n^3) O(n3)。

2、背包與樹形DP

  有一些樹形DP問題，可以抽象為背包問題，被稱為“樹形依賴的背包問題”。例如上面的題目“二叉蘋果樹”，可以模組化為“分組背包”（注意與普通分組背包的差別是，這裡的每個組可以選多個物品，而不是一個）：

  （1）分組。根結點u的每個子樹是一個分組。

  （2）背包的容量。把u為根的整棵樹上的樹枝數，看成背包容量。

  （3）物品。把每個樹枝看成一個物品，體積為1，樹枝上的蘋果數量看成物品的價值。

  （4）背包目标。求能放到背包的物品的總價值最大，就是求留下樹枝的蘋果數最多。

  如果讀者做個對比，會發現分組背包的代碼和“二叉蘋果樹”的代碼很像，下面貼出2個代碼幫助了解。

  （1）分組背包的代碼。參考本章“經典DP面試問題”的分組背包例題hdu 1712。

for(int i = 1; i <= n; i++)                 //周遊每個組
    for(int j = C; j>=0; j--)               //背包總容量C
        for(int k = 1; k <= m; k++)         //用k周遊第i組的所有物品
            if(j >= c[i][k])                //第k個物品能裝進容量j的背包
               dp[j] = max(dp[j], dp[j-c[i][k]] + w[i][k]);    //第i組第k個
           

  （2）樹形dp代碼。下面是洛谷P2015部分代碼。

for(int i = 0; i < edge[u].size(); i++) {    //把u的每個子樹看成一個組
    ......
    for(int j = sum[u]; j >= 0; j--)         //把u的枝條總數看成背包容量
        for(int k = 0; k <= j - 1; k++)      //用k周遊每個子樹的每個枝條
            dp[u][j] = max(dp[u][j], dp[u][j-k-1] + dp[v][k] + w);
           

  需要注意的是，代碼（1）和代碼（2）的j循環都是從大到小，具體原因已經在對應的章節中詳細解釋。

  樹形背包問題的狀态定義，一般用dp[u][j]表示以點u為根的子樹中，選擇j個點（或j個邊）的最優情況。

  下面給出一個經典題，請讀者自己分析和編碼。

有線電視網 洛谷P1273（poj 1155）https://www.luogu.com.cn/problem/P1273

題目描述：某收費有線電視網計劃轉播一場足球比賽。他們的轉播網和使用者終端構成一棵樹狀結構，這棵樹的根結點位于足球比賽的現場，樹葉為各個使用者終端，其他中轉站為該樹的内部節點。

  從轉播站到轉播站以及從轉播站到所有使用者終端的信号傳輸費用都是已知的，一場轉播的總費用等于傳輸信号的費用總和。

  現在每個使用者都準備了一筆費用想觀看這場精彩的足球比賽，有線電視網有權決定給哪些使用者提供信号而不給哪些使用者提供信号。

  寫一個程式找出一個方案使得有線電視網在不虧本的情況下使觀看轉播的使用者盡可能多。

輸入格式：輸入檔案的第一行包含兩個用空格隔開的整數N和M，其中2 ≤ N ≤ 3000，1 ≤ M ≤ N-1，N為整個有線電視網的結點總數，M為使用者終端的數量。

  第一個轉播站即樹的根結點編号為1，其他的轉播站編号為2到N-M，使用者終端編号為N-M+1到N。

  接下來的N-M行每行表示—個轉播站的資料，第i+1行表示第i個轉播站的資料，其格式如下：

     K A1 C1 A2 C2 … Ak Ck

  K表示該轉播站下接K個結點(轉播站或使用者)，每個結點對應一對整數A與C，A表示結點編号，C表示從目前轉播站傳輸信号到結點A的費用。最後一行依次表示所有使用者為觀看比賽而準備支付的錢數。

輸出格式：輸出檔案僅一行，包含一個整數，表示上述問題所要求的最大使用者數。

輸入樣例：

5 3

2 2 2 5 3

2 3 2 4 3

3 4 2

輸出樣例：

2

  此題和例題“洛谷P2015”類似。

  定義dp[u][j]：以u為根的子樹上有j個使用者時的最小費用。計算結束後，使dp[1][j] ≤ 0的最大j就是答案。

  狀态轉移方程：dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k] + w)，與例題“洛谷P2015”的狀态轉移方程幾乎一樣。

3、應用示例：樹的重心

   樹的最大獨立集、重心、最長點對是常見的問題2。下面給出樹的重心的一個例題。本題的代碼，用鍊式前向星來存樹。

Godfather poj 3107 http://poj.org/problem?id=3107

題目描述： 城裡有一個黑手黨組織。把黑手黨的人員關系用一棵樹來描述，教父是樹的根，每個結點是一個黑手黨徒。為了保密，每人隻和他的父結點和他的子結點聯系。警察知道哪些人互相來往，但是不知他們的關系。警察想找出誰是教父。

   警察假設教父是一個聰明人：教父懂得制衡手下的權力，是以他直屬的的幾個小頭目，每個小頭目屬下的人數差不多。也就是說，删除根之後，剩下的幾個互不連通的子樹（連通塊），其中最大的連通塊應該盡可能小。幫助警察找到哪些人可能是教父。

輸入格式：第一行是n，表示黑手黨的人數，2 ≤ n ≤ 50 000。黑手黨徒的編号是1到n。下面有n-1行，每行有2個整數，即有聯系的2個人的編号。

輸出格式：輸出疑為教父的結點編号，從小到大輸出。

輸入樣例：

6

1 2

2 3

2 5

3 4

3 6

輸出樣例：

2 3

  樹的重心u是這樣一個結點：計算樹上所有結點的子樹的結點數，如果結點u的最大的子樹的結點數最少，那麼u就是樹的重心。本題中的教父就是樹的重心。

  首先考慮一個基本問題：如何計算以結點i為根的樹的結點數量？對i做DFS即可，從i出發，遞歸到最底層後傳回，每傳回一個結點，結點數加1，直到所有結點都傳回，就得到了樹上結點總數。因為每個結點隻傳回1次，所有這個方法是對的。

  回到本題，先考慮暴力法。删除樹上的一個結點u，得到幾個孤立的連通塊，可以對每個連通塊做一次DFS，分别計算結點數量。對整棵樹逐一删除每個結點，重複上述計算過程，就得到了每個結點的最大連通塊。

  暴力法過于笨拙，其實并不需要真的一個個去删除每個結點，更不需要對每個連通塊分别做DFS。隻需要一次DFS，就能得到每個結點的最大連通塊。用下面的圖解釋這個過程。

圖1 删除結點u得到三個連通塊

  觀察結點u。删除u後，得到三個連通塊：（1）包含1的連通塊；（2）包含2 的連通塊，（3）包含3的連通塊。這三個連通塊的數量如何計算？

  對左圖做DFS。可以從任意一個點開始DFS，假設從1開始，1是u的父結點。DFS到結點u後，從u開始繼續DFS，得到它的子樹2和3的結點數量（2）和（3），設u為根的子樹的數量是d[u]，則d[u] = (2) + (3) + 1。那麼（1）的數量等于n - d[u]，n是結點總數。記錄（1）、（2）、（3）的最大值，就得到了u的最大連通塊。

  這樣通過一次DFS，每個結點的最大連通塊都得到了計算。

  本題的n很大，用鍊式前向星存樹能有效節省空間。

poj 3107的代碼（鍊式前向星存樹）

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 50005;          //最大結點數
struct Edge{
    int to, next;
}edge[N<<1];                  //兩倍：u-v, v-u
int head[N], cnt = 0;
void init(){                  //鍊式前向星：初始化
    for(int i=0; i<N; ++i){
        edge[i].next = -1;
        head[i] = -1;
    }
    cnt = 0;
}
void addedge(int u,int v){    //鍊式前向星：加邊u-v
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
int n;
int d[N], ans[N], num=0, maxnum=1e9;       //d[u]: 以u為根的子樹的結點數量
void dfs(int u,int fa){                        
    d[u] = 1;                              //遞歸到最底層時，結點數加1
    int tmp = 0;
    for(int i=head[u]; ~i; i=edge[i].next){ //周遊u的子結點。~i 也可以寫成 i != -1
        int v = edge[i].to;                //v是一個子結點
        if(v == fa) continue;              //不遞歸父親
        dfs(v,u);                          //遞歸子節點，計算v這個子樹的結點數量
        d[u] += d[v];                      //計算以u為根的結點數量
        tmp = max(tmp,d[v]);               //記錄u的最大子樹的結點數量
    }
    tmp = max(tmp, n-d[u]);                //tmp = u的最大連通塊的結點數
    //以上計算出了u的最大連通塊
    //下面統計疑似教父。一個結點的最大連通塊比其他結點都小，是疑似教父
    if(tmp < maxnum){                      //一個疑似教父
        maxnum = tmp;                      //更新“最小的”最大連通塊 
        num = 0;
        ans[++num] = u;                    //把教父記錄在第1個位置
    }
    else if(tmp == maxnum)                 //疑似教父有多個，記錄在後面
        ans[++num] = u;    

}
int main(){
    scanf("%d",&n);
    init();
    for(int i=1; i<n; i++){
        int u, v;      scanf("%d %d", &u, &v);
        addedge(u,v);  addedge(v,u);
    }
    dfs(1,0);
    sort(ans+1, ans+1+num);
    for(int i=1;i<=num;i++)   printf("%d ",ans[i]);
}
           

4、樹形DP習題

  上面用幾個簡單例題介紹了樹形DP的基本操作。樹形DP的題目往往很難，請讀者多練習。下面是一些經典題。

  （1）經典題hdu 1520，hdu 2196 computer，在《算法競賽入門到進階》中有詳細講解。

  （2）樹形背包：poj 1947，poj 2486， hdu 1011，hdu 1561，hdu 4003。

  （3）樹的最大獨立集、重心、最長點對：UVa 12186、UVa1220、UVa 1218。

  （4）删點和删邊：hdu 3586，poj 2378，poj 3140。

  （5）poj 2152，poj 3162。

1. 《算法競賽入門到進階》清華大學出版社，羅勇軍，郭衛斌，“10.2 圖的存儲”詳細介紹了鄰接表和鍊式前向星。 ↩︎
2. 《算法競賽入門經典第2版》劉汝佳，清華大學出版社，280頁。詳細講解了這3種場景，并給出了幾個習題：UVa 12186、UVa1220、UVa 1218。 ↩︎