詳解樹形DP

Posted on by

前言

給定一顆有N個節點的樹（一般是無根樹，就有N-1條無向邊），可以任選一個節點作為根節點

一般以節點從深到淺（子樹從小到大）的順序作為dp階段順序

dp的狀態表示中，第一維通常是節點編號（節點編號代表瞭以該節點為根的子樹）

對於每個節點x，先遞歸在它的每個子節點上進行dp，回溯時，從子節點向x進行狀態轉移

A – Anniversary part

N個員工，編號為1~N

他們之間有從屬關系，也就是說他們的關系就像一棵以校長為根的樹，父結點就是子結點的直屬上司。現在有個宴會，宴會每邀請來一個員工 i 都會增加一定的快樂指數 Ri，但如果某個員工的直屬上司來瞭，那麼這個員工就不會來。計算邀請哪些員工可以使快樂指數最大，輸出最大的快樂指數

設 dp [x] [0] 表示在 x 為根的子樹中邀請部分員工，並且 x 不參加時，快樂指數總和的最大值，此時 x 子節點（直接下屬）可以參加也可以不參加 (s表示x子節點)

設 dp [x] [1] 表示在 x 為根的子樹中邀請部分員工，並且 x 參加時，快樂指數總和的最大值，此時 x 子節點（直接下屬）都不能參加，H[x] 表示當前節點（x）的快樂指數 (s表示x子節點)

這個題給的是有根樹，就可以從根節點開始，dp目標就是 max(F[root,0] , F[root,1]) 時間復雜度ON

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> son[10010];
int dp[10010][2];//0不參加，1參加
int v[10010];//記錄有沒有父節點
int h[10010];//記錄快樂指數
int n;

void DFS(int x){
    dp[x][0] = 0;
    dp[x][1] = h[x];
    for (int i = 0; i < son[x].size(); i++)
    {
        int y = son[x][i];
        DP(y);
        dp[x][0] += max(dp[y][0],dp[y][1]);
        dp[x][1] += dp[y][0];
    }
}

int main(){
    cin>>n;
    for (int i = 1; i <=n ; i++)
        scanf("%d",&h[i]);
    for (int i = 1; i <n ; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x] = 1;//x有爸爸
        son[y].push_back(x);//x是y的子節點
    }
    int root;
    for (int i = 1; i <= n; i++)
        if(!v[i]){ //i沒有爸爸
            root = i;
            break;
        }
    DFS(root);
    cout << max(dp[root][0],dp[root][1]) << endl;
    return 0;
}

B – Strategic game

有n個點，在某些點上放置哨兵，每個哨兵可以監控和它有邊相連的點，問監視所有的點需要的最少的哨兵數

也就是說一顆n個結點的樹，要求選出其中的一些頂點，使得對於樹中的每條邊(u, v)，u和v至少有一個被選中，要求給出選中頂點數最少的方案

設 dp [x] [0] 表示在不選擇節點 x 的情況下，以 x 為根節點的子樹，最少需要選擇的節點數

​當i為葉子節點時

​當i不為葉子節點時 (s表示x子節點)

設 dp [x] [1] 表示在選擇節點 x 的情況下，以 x 為根節點的子樹，最少需要選擇的節點數
​當i為葉子節點時

​當i不為葉子節點時 (s表示x子節點)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 1508
using namespace std;

int dp[maxn][2];
int soncnt[maxn];
int parent[maxn];
int n;

void DFS(int x) {
    int i, d1=0, d0=0;
    if (soncnt[x] == 0) {
        dp[x][0] = 0;
        dp[x][1] = 1;
        return;
    }
    for (i=0; i < n; i++) {
        if (parent[i] == x) {
            DFS(i);
            d1 += min(dp[i][0], dp[i][1]);
            d0 += dp[i][1];
        }
    }
    dp[x][1] = d1 + 1;
    dp[x][0] = d0;
}

int main() {
    int dad, son, m;
    while (cin >> n) {
        memset(soncnt, 0, sizeof(soncnt));
        memset(parent, -1, sizeof(parent));
        int root = -1;
        for (int i = 0; i < n; i++) {
            scanf("%d:(%d)", &dad, &m);
            soncnt[dad] = m;
            if (root == -1) {
                root = dad;
            }
            while (m--) {
                scanf("%d", &son);
                parent[son] = dad;
            }
        }
        DFS(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}

C – Tree Cutting

給一顆n個結點的樹，節點編號為1~n

問：刪除哪些結點後，剩餘各個子樹的大小均小於原總結點數的一半

拆除一個節點後，剩餘部分為其若幹兒子的子樹以及該節點上層所連其餘部分（n-size[i]），隻要這些連接塊大小都不超過n/2，該節點就滿足條件。因而我們可以先求出每個節點所管轄的那棵樹的大小，自下而上地為每個節點求出其子樹規模（該點規模=其兒子的規模和+1）。

在建樹的時候可以直接用連接表（vector）儲存無向邊，這時由於無法區分與每個點相連的是其父節點還是子節點，會引發問題：在dfs的時候把父節點誤認作兒子節點，解決方法就是在遞歸的時候傳入父節點編號，然後在遞歸，計算規模，比較大小的時候避開它就可以瞭

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n;
int root;
vector<int>G[10000+400];
vector<int>ans;
int sz[10000+400];
 
void dfs(int par,int u){
    sz[u]=1;
    for(int i=0;i<(int)G[u].size();i++){
        if(G[u][i]!=par)
            dfs(u,G[u][i]);
    }
    int piece=0;
    for(int i=0;i<(int)G[u].size();i++)
        if(par!=G[u][i]){
            sz[u]+=sz[G[u][i]];
            piece=max(piece,sz[G[u][i]]);
        }
    piece=max(piece,n-sz[u]);
    if(piece<=n/2)
        ans.push_back(u);
}
 
int main(){
    while(cin>>n){
        memset(sz,0,sizeof(sz));
        int x,y;
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(0,1);
        sort(ans.begin(),ans.end());
        for(int i=0;i<(int)ans.size();i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}

LCA 最近公共祖先

倍增（基於二分的方法）

假如樹上的兩個點，處於同一深度時，對於往上跳mid步，顯然有單調性：

如果它們往上跳mid步是同一個點，則這個點是它們的共同祖先，但不一定是最近公共祖先

那麼如果我們可以快速得到每個點往上跳若幹步是誰，顯然我們可以利用二分來求LCA

這個可以用倍增來做。

倍增的思想其實非常簡單，就是利用二進制的思想。一個顯然的結論有：

節點u往上跳2^(k+1)的佈的祖先 = （節點u往上跳2k佈的祖先）往上跳2k佈的祖先

用代碼表示就是：

fa[u][k + 1] = fa[ fa[u][k] ][k];

這個的預處理也非常簡單，我們隻需要初始化每個fa[u][0]就可以瞭就可以瞭，因為接下來的部分都可以根據上面的公式遞推。

然後預處理好這個之後，我們就可以根據這個進行二分瞭，代碼如下：

int fa[maxn][20], dep[maxn];

void dfs(int u, int f, int d)
{
    dep[u] = d;
    fa[u][0] = f;
    for(int i = 1; i < 20; ++i)
    {
        fa[u][i] = fa[fa[u][i -  1]][i] - 1;
    }
    for(int i = head[u]; ~i; i = nxt[i])
    {
        int t = to[i];
        if(t != f)
        {
            dfs(t, u, d + 1);
        }
    }
}

int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < k; ++i)
    {
        if((1 << i) & k) u = fa[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; --i)
    {
        if(fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

以上就是詳解樹形DP的詳細內容，更多關於樹形DP的資料請關註WalkonNet其它相關文章！

推薦閱讀：