树上背包优化 - 时间复杂度证明
树上背包优化 - 时间复杂度证明
- 例题
- 树上背包顾名思义，就是在树上做背包 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]; // 注意这里！
}
}
- 其实这个优化就是利用子树的背包中有效最大值和有效最小值来优化
时间复杂度证明
- 根据代码，每个节点 \(u\) 的时间复杂度是：\(sz_{v1} + sz_{v2} \times sz_{v1} + sz_{v3} \times (sz_{v1} \cdot sz_{v2}) + sz_{v4} \times (sz_{v1} \cdot sz_{v2} \cdot sz_{v3}) + \cdots\)
- 设 \(sum(x)\) 表示 \(sz_{v1} \cdot sz_{v2} \cdot sz_{v3} \cdots sz_{v_{x-1}} \cdot sz_{vx}\)
- 则一开始的多项式可以化为：\(sum(1) + sum(2) + sum(3) + sum(4) + \cdots\)
感性理解：
- 可以将 \(dp\) 数组的第二维单独看
- 那么一共会有 \(n \times n\) 次合并
- 如果用 \(size\) （大小）来约束枚举的状态，就可以保证没有枚举多余的转移
- 每个状态枚举一次