树形DP

树形dp是在树结构上进行动态规划的方法，通过从叶子节点到根节点（或相反）进行状态转移来解决问题

基本思想

分析父树得到答案需要子树的哪些信息
把子树信息的全集定义成递归返回值
通过递归让子树返回全集信息
整合子树的全集信息得到父树的全集信息并返回

模板

vector<int> tree[N];  // 邻接表存树
int dp[N];            // DP状态数组
void dfs(int u, int fa) {
    // 初始化当前节点的状态
    dp[u] = val[u];  // 或其他初始值
    
    // 遍历所有子节点
    for (int v : tree[u]) {
        if (v != fa) {  // 避免回到父节点
            dfs(v, u);  // 递归处理子树
            
            // 状态转移（根据具体问题）
            dp[u] += dp[v];  // 例如：累加子树贡献
        }
    }
    
    // 可以在这里进行一些后处理操作
}

换根DP

换根DP适用于处理以每个节点为根时的情况

使用场景

求每个节点作为根时的某个值
- 每个节点的子树大小
- 每个节点到其他所有节点的距离和
- 每个节点为根时的最大独立集
涉及整棵树的全局信息
- 树的直径
- 树的重心

核心思想

通常使用两个DFS：

第一个dfs以1为根，计算每个节点的子树内的信息，从而得到以节点1为根时的答案
第二个dfs进行换根，将根从父节点移动到子节点，更新相关信息并计算新根答案

模板

// 第一遍DFS：计算以1为根的信息
void dfs1(int u, int fa) {
    // 初始化状态
    for (int v : tree[u]) {
        if (v != fa) {
            dfs1(v, u);
            // 更新u的状态基于v的信息
        }
    }
}

// 第二遍DFS：换根计算所有节点答案
void dfs2(int u, int fa) {
    // 计算当前节点的答案
    ans[u] = ...;
    
    for (int v : tree[u]) {
        if (v != fa) {
            // 换根公式：从u换到v
            // 更新v的向上信息
            dfs2(v, u);
        }
    }
}

树上背包

树上背包是在树形结构上应用背包思想，用于解决树的子树中进行资源分配，选择限制等问题

本质是在每个节点的子树中进行背包选择，将子树的结果合并到当前节点

核心思想

DFS遍历：从叶子节点向根节点进行
子树合并：将每个子树的背包结果合并
状态转移：在容量限制下选择最优组合

对于考虑某个子树的根节点x，有两个选择：
- 不选自己
- 选自己，考虑自己的子树

分析

给定一棵$n$个节点的有根树，编号为1到$n$ ，1号点为根节点且每个节点$i$有价值$v_i$，体积$w_i$ 。背包容量为$m$，在满足如果$u$选了，则其所有祖先$v$都要选的限制下，使选择的物品组合总价值和最大。

$O(nm^2)$

定义$f_{x,j}$为在根节点x中，选择j个节点的最大值，根据两个选择：

若不选自己，则$f_{x,j}=0$
若选自己，则$f_{x,j}=w_i+f(a,k_a)+\cdots$

即根节点的价值+子节点a中选$k_a$个节点的最大值

这样转移较为麻烦，我们可以将根节点与其孩子看作一个集合，把里面每个点看作物品，问题就转化为了上面所述问题

若为根节点：$w_i=1, v_i=当前v_i$
若为子节点：$w_i=k(k\leq 子树大小), v_i=f(v_i, v_i大小, k)$

$f(x,i,j)=\left\{\begin{matrix} f(x,i-1,j)&不选\\f(x,i-1,j-k)+f(v_i, v_i的大小,k) & 选\end{matrix}\right.$

$(0\leq k<j)$，取max

状态转移方程

$$ { \[\begin{matrix} f(x,i,j)=\max\{f(v,v的孩子数,k)+f(x,i-1,j-k)\} \\ f(x,1,1)=根节点价值 \\ f(x,1,0)=0 \end{matrix}\]

. $$

例

洛谷P2014 选课

使用树建模，把每门课与自己的直接先修课连一条边

使用树上背包进行求解

时间复杂度：$O(n^3)$

int n, m;
int val[N];
int dp[N][N][N];
vector<int> g[N];
void dfs(int u){
  for (auto v:g[u]){
    dfs(v);
  }
  dp[u][1][0] = 0;
  dp[u][1][1] = val[u];
  for (int i = 2; i<=g[u].size()+1;i++){
    int v = g[u][i-2];
    for (int j = 0; j<=n; j++){
      for (int k = 0; k<j;k++){
        dp[u][i][j] = max(dp[u][i][j], dp[v][g[v].size()+1][k]+dp[u][i-1][j-k]);
      }
    }
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);


  }
  dfs(0);
  cout << dp[0][g[0].size()+1][m+1];
  
}

优化1

当我们计算$f[x][i]$时，使用的是前i个物品的节点个数，即前i个子树大小之和

故我们可以将dfs放入主循环，同时记录子树大小

将j的循环终止条件设为子树大小

时间复杂度：$O(n^3)$

int n, m;
int val[N];
int dp[N][N][N];
int cnt[N];
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  dp[u][1][0] = 0;
  dp[u][1][1] = val[u];
  for (int i = 2; i<=g[u].size()+1;i++){
    int v = g[u][i-2];
    dfs(v);
    cnt[u] +=cnt[v]; // 记录子树大小
    
    for (int j = 0; j<=cnt[u]; j++){
      for (int k = 0; k<min(cnt[v]+1,j);k++){ // k不超过子节点子树大小
        dp[u][i][j] = max(dp[u][i][j], dp[v][g[v].size()+1][k]+dp[u][i-1][j-k]);
      }
    }
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);


  }
  dfs(0);
  cout << dp[0][g[0].size()+1][m+1];
}

优化2

更改递推方式：

求当前问题时使用已经求过的答案 -> 用已经求好的答案更新未来的问题

$f(x,i+1,j+k)=\max\{f(v,v的孩子数,k)+f(x,i,j\}$

同时可以用滚动数组优化空间复杂度

时间复杂度：$O(n^2)$

证明略，见视频

int n, m;
int val[N];
int dp[N][N];
int cnt[N];
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  dp[u][0] = 0;
  dp[u][1] = val[u];
  for (int i = 1; i<g[u].size()+1;i++){
    int v = g[u][i-1];
    dfs(v);
    
    
    for (int j = cnt[u]; j>=0; j--){
      for (int k = cnt[v]; k>=0;k--){
        if(k==0||j>0) dp[u][j+k] = max(dp[u][j+k], dp[v][k]+dp[u][j]);
      }
    }
    cnt[u] +=cnt[v];
  }
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);
  }
  dfs(0);
  cout << dp[0][m+1];
}

DFS序

我们采用后序遍历来遍历树，则有着特殊的性质：

孩子在自己的前面
第一个孩子 = 自己的编号-1
第二个孩子 = 自己的编号-第一个孩子的大小
自己的编号-自己的大小 = 自己兄弟的编号

我们设$f(i,j)$是考虑当前节点i和自己前面兄弟中选择j个节点的最大值

x是后序遍历编号i对于原来的节点编号

则状态转移方程为： \[ f(i,j)=\max\left\{\begin{matrix} f(i-1,j-1)+s_x & j>0\\f(i-cnt_x,j)\end{matrix}\right. \]

int n, m;
int val[N];
int dp[N][N];
int cnt[N];
int num[N];
int tot = 0;
vector<int> g[N];
void dfs(int u){
  cnt[u] = 1;
  for(auto v: g[u]){
    dfs(v);
    cnt[u]+=cnt[v];
  }
  num[++tot] = u;
}
void solve() {
  
  cin >> n >>m;
  for (int i = 1; i<=n; i++){
    int u;
    cin >> u >> val[i];
    g[u].push_back(i);
  }
  dfs(0);
  for (int i = 1; i<=n; i++){
    for (int j = 0; j<=m; j++){
      if(j>0) dp[i][j] = max(dp[i-1][j-1]+val[num[i]], dp[i-cnt[num[i]]][j]);
    }
  }
  cout << dp[n][m];
}

红魔咖啡馆

【动态规划】树形DP

树形DP

基本思想

模板

换根DP

使用场景

核心思想

模板

树上背包

核心思想

分析

\(O(nm^2)\)

状态转移方程

例

优化1

优化2

DFS序