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

树上背包顾名思义，就是在树上做背包 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]);
			}
		}
	}
}