动态规划-树形DP

参考资料：树形 DP - OI Wiki

树形DP

树形 DP，即在树上进行的DP。由于树固有的递归性质，一般通过递归DFS（或 BFS） 进行

基础

P1352 没有上司的舞会 - 洛谷 某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

不妨设 \(f(i,0/1)\) 表示以 \(i\) 为根的子树当其根节点的值 取/不取 的最优解（ \(0\) 表示 \(i\) 不去舞会，反之要去）

对于每个状态，都存在两种决策（以下 \(x\) 为 \(i\) 的所有儿子）

  • 上司不参加舞会时，下属可以参加，也可以不参加，是否参加取决于所能产生的最大快乐值，因此有

\[ f(i,0) = \sum max(f(x,0),f(x,1)) \]

  • 上司参加舞会时，下属只能不参加，但下属的下属则未必

\[ f(i,1) = a_i + \sum f(x,0) \]

这里，设上司结点是其所有下属结点的父结点，找到总上司结点为根节点，从根节点 DFS 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>

using namespace std;

const int N = 1e4;
long long dp[N][2];
int a[N]; //记录快乐值
int v[N]; //是否为子节点
vector<int> g[N]; //存放图

void dfs(int x){ //递归求dp
    dp[x][0] = 0;
    dp[x][1] = a[x];
    for(auto i : g[x]){
        dfs(i); //先得到dp[i][0/1]
        dp[x][0] += max(dp[i][0],dp[i][1]);
        dp[x][1] += dp[i][0];
    }
}


int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<n-1;i++){
        int l,k;
        cin >> l >> k;
        g[k].push_back(l);
        v[l] = 1;
    }
    int root;
    for(int i=1;i<=n;i++){
        if(!v[i]){
            root = i; //找到根节点
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0],dp[root][1]);
}

树上背包

P2014 [CTSC1997] 选课

有 $N$ 门功课，每门课有若干学分，分别记作 $s_1,s_2,\cdots,s_N$，每门课有一门或没有直接先修课（若课程 $a$ 是课程 $b$ 的先修课即只有学完了课程 $a$，才能学习课程 $b$）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

每门课最多只有一门先修课的特点，与有根树中最多只有一个父亲节点的特点类似。

因此可以想到根据这一性质建树，从而所有课程组成了一个森林结构。为了方便起见，我们可以新增一门 0学分的课程 （设其编号为 \(0\) ），作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以 \(0\) 号课程为根的树。

我们设 \(f(u,k,j)\) 比表示以 \(u\) 号点为根的子树中，已经遍历了 \(u\) 号点的前 \(k\) 棵子树，选了 \(j\) 门课程的最大学分。

转移的过程结合了树形 DP 和背包 DP 的特点，我们枚举 \(u\) 点的每个子结点 \(v\) ，同时枚举以 \(v\) 为根的子树选了几门课程，将子树的结果合并到 \(u\) 上。

记 \(x\) 的儿子个数为 \(s_x\) ，以 \(x\) 为根的子树大小为 \(siz_x\) ，可以写出下面的状态转移方程： \[ f(u,i,j) = \max \limits_{v,k\leq j,k\leq siz_v} f(u,i-1,j-k)+f(v,s_v,k) \] 注意上面状态转移方程的几个限制条件，这些条件确保了一些无意义的状态不会被访问到。

\(f\) 的第二维可以很轻松地用滚动数组的方式省略掉，注意这时需要倒序枚举 \(j\) 的值。

该做法的时间复杂度为 \(O(nm)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

using namespace std;

const int N = 310;
int s[N];
int dp[N][N];
vector<vector<int>> g(N);
int n,m;
int dfs(int u){
    int p = 1;
    dp[u][1] = s[u];
    for(int i=0;i<g[u].size();i++){
        int v = g[u][i];
        int tmp = dfs(v);
        p += tmp;
        for(int j=min(p,m+1);j>=1;j--){
            for(int k=1;k<j&&k<=tmp;k++){
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);
            }
        }
    }
    return p;
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int k;
        cin >> k >> s[i];
        g[k].push_back(i);
    }
    dfs(0);
    cout << dp[0][m+1];
}

换根DP

顾名思义，换根DP涉及到根结点的选择，通常其题目要求以各个结点作为根节点来解决问题，并且其中根节点的变化对于一些值，例如子结点深度和、点权和等产生影响。

换根DP问题又被称作二次扫描，通常需要两次 DFS ，第一次预处理诸如深度，点权和等信息，第二次开始进行DP。

[POI 2008] STA-Station 给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。 一个结点的深度之定义为该节点到根的简单路径上边的数量。
由于根节点不会被指定，显然建边时应当按无向边来建，注意遍历时要判断父子关系。

在一个树结构中，如果让原根为 \(u\) 的树，把根 “换” 为其子结点 \(v\) ，会发生什么呢？

显然有

  • 所有在 \(v\) 的子树上的结点深度都减少了一，那么总深度就减少了 \(v\) 的子树的结点个数 \(s_v\)
  • 所有不在 \(v\) 子树上的结点深度都增加了一，那么总深度和就增加了 \(n-s_v\)

那么现在，我们显然知道： 我们需要先通过深搜预处理得到以 \(i\) 为根的子树中的结点个数 （这显然为 \(s_u = 1+\sum s_v\) ）。然后通过深搜去做DP得到对应深度 ，最后遍历找深度最大的结点编号即可。

由于此题无需找到最大深度，只用让 \(dp\) 表示为与自己设置的根节点（如1）的偏差即可。否则，还需要记录该根节点的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+10;
#define int long long
vector<vector<int>> g;
int s[N];
int dp[N];
int n;

int dfs(int u,int f){
    int p = 1;
    for(int v:g[u]){
        //避免循环调用
        if(v==f) continue; 
        p += dfs(v,u);
    }
    s[u] = p;
    return p;
}

//如果以u的子节点v作为新的根
//那么子树的所有结点的深度均减一，共减去dp[v]
//那么其它所有结点的深度均加一，共增加n-dp[v];
//显然，相比下增加最多的为最优根
//由于只用比较，不用管其中的具体值
//dp[v] = dp[u]+n-2*s[v];
void get_ans(int u,int f){
    for(auto v:g[u]){
        if(v!=f){
            dp[v] = dp[u]+n-2*s[v];
            get_ans(v,u);
        }
    }
}

signed main(){
    cin >> n;
    g.resize(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        //由于无指定根节点，要建双向边
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //预处理以1为root时的结点个数
    dfs(1,1);
    dp[1] = 0;
    //如果需要记录最大深度，要得到设置的根的深度和
    for(int i=1;i<=n;i++) dp[1] += s[i]; 
    get_ans(1,1);
    int mx = 1;
    for(int i=1;i<=n;i++){
        if(dp[i]>dp[mx]){
            mx = i;
        }
    }
    cout << mx;
    return 0;
}