樹形DP的經典運用

樹形DP一般用于一些樹形結構的題目，而且是算法競賽中比較喜歡考察的一個知識點。

樹形DP入門

例題1：AcWing 285.沒有上司的舞會

這題非常簡單，可稱之為樹形DP的入門題。顯然，一個節點有兩種狀态：選（參加）或不選（不參加）。那麼不妨設fu,1表示節點u被選後u節點及其子樹可獲得的最大權值，fu,0表示節點u不被選的情況下，u節點及其子樹可獲得的最大權值。那麼很容易可以推出：fu,1（+=fson,0）+wu（其中son表示u的所有子節點）。fu,0+=max(fson,1,fson,0)。那麼這個DP順序顯然要按照dfs的順序來按深度周遊，而且要用遞歸的方式先求出子節點的狀态。是以代碼就很容易寫了：

#include<iostream>
using namespace std;
const int N=6005;
int h[N],f[N][2];
int head[N],to[N],ne[N],idx;
bool hfa[N];
void add(int x,int y){
    ne[++idx]=head[x];
    to[idx]=y;
    head[x]=idx;
}
void dfs(int u){
    f[u][1]=h[u];
    for(int i=head[u];i;i=ne[i]){
        int j=to[i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        hfa[a]=true;
        add(b,a);
    }
    int root=1;
    while(hfa[root]) root++;//尋找根節點
    dfs(root);
    cout<<max(f[root][1],f[root][0]);
}
           

背包類樹形DP

例題1：AcWing 286.選課

這題與上一題略有不同，這題限定了學生選課的數量剛好為m。是以這題還需要将選課數量也作為狀态的一個次元。那麼不妨設fx,t表示在以x為根節點的子樹中（包括x）選恰好t門課可獲得的最大學分。

特别地，當t=0時，x的子樹中沒有可選的課，故fx,0=0

當t>0時，設Son(x)為x的子節點集合，則fx,t= ∑ i = 1 p f y i , c i \sum_{i=1}^{p} f_{y_{i},c_{i}} ∑i=1p​fyi​,ci​​+creditx（其中yi ∈ \in ∈Son(x)，且 ∑ i = 1 p c i = t − 1 \sum_{i=1}^{p} c_{i}=t-1 ∑i=1p​ci​=t−1）。

那麼這個式子的形式很像之前線性DP中講到的分組背包DP。我們不妨這樣了解：

一共有p個組，每個組裡有若幹個物品，物品的編号為yi，體積為ci，權值為fyi,ci，背包的體積是t-1，且每個組裡最多挑一個物品。這樣，思路就很明朗了，代碼如下：

#include<iostream>
using namespace std;
const int N=305;
int head[N],to[N],ne[N],w[N],idx;
int f[N][N];
int n,m;
void add(int x,int y){
    ne[++idx]=head[x];
    to[idx]=y;
    head[x]=idx;
}
void dfs(int u){
    for(int i=head[u];i;i=ne[i]){
        dfs(to[i]);
        for(int j=m-1;j;j--){
            for(int k=1;k<=j;k++){
                f[u][j]=max(f[u][j],f[u][j-k]+f[to[i]][k]);
            }
        }
    }
    for(int i=m;i>=1;i--){
        f[u][i]=f[u][i-1]+w[u];
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x>>w[i];
        add(x,i);
    }
    m++;
    dfs(0);
    cout<<f[0][m]<<endl;
    return 0;
}
           

二次掃描與換根法

例題1:AcWing 287.積蓄程度

這個題目中給的樹是一個無根樹，需要對根進行枚舉，但顯然O(n2)的複雜度無法接受，是以我們引入了二次掃描與換根法：先考慮以任意一個點為根節點去求答案，将得到的答案記為Droot。那麼這個時候我們就要考慮怎麼求出任意的Fi（即以i為根節點的總流量）：

這個時候考慮對于任意一個節點x的子節點y，假設我們此時已經求出了Fx，那麼應該如何導出Fy呢？其實很簡單：（直接看藍書P294就懂了）

總結：二次掃描與換根法的精髓在于先由下到上做一遍dfs求出Droot，然後利用D數組由上到下再做一遍dfs求出Fi