树上背包优化 - 时间复杂度证明

• 例题
• 树上背包顾名思义，就是在树上做背包 dp
• 树上背包的模板代码如下

void dfs(int x){
	sz[x] = 1;
	if(x >= n - m + 1){
		dp[x][1] = -a[x];
		return;
	}
	for(PII e : eg[x]){
		int nxt = e.first;
		dfs(nxt);
		sz[x] += sz[nxt];
		for(int j = m; j >= 0; j--){
			for(int h = 1; h <= j; h++){
				dp[x][j] = min(dp[x][j], dp[x][j - h] + e.second + dp[nxt][h]);
			}
		}
	}
}

• 但是这样的循环显然是 \(O(n^3)\) 的
• 这有一种固定的优化方法，可以将这三个循环优化到理论 \(O(n^2)\)

优化

void dfs(int x){
  if(x >= n - m + 1){
    dp[x][1] = -a[x];
    sz[x] = 1;
    return;
  }
  for(PII e : eg[x]){
    int nxt = e.first;
    dfs(nxt);
    for(int j = sz[x]; j >= 0; j--){
      for(int h = sz[nxt]; h >= 0; h--){
        dp[x][j + h] = min(dp[x][j + h], dp[x][j] + e.second + dp[nxt][h]);
      }
    }
    sz[x] += sz[nxt];
  }
}