树形背包问题

一些题目给定了树形结构，在这个树形结构中选取一定数量的点或边（也可能是其他属性），使得某种与点权或者边权相关的花费最大或者最小。解决这类问题，一般要考虑使用树上背包。

树上背包，顾名思义，就是在树上做背包问题。一个节点的若干子树可以看作是若干组背包，也就是用树形dp的方式做分组背包问题。一般来说，f ( i , j ) f(i,j)f(i,j)表示以i ii为根的子树中，在j jj的容量范围内，最大或者最小可以获得多少收益。根据分组背包的思想，第一维枚举物品（在树上指的是子树），第二维枚举容量，第三维枚举决策（这里指的是给子树分配多少容量）。基本的代码框架如下：

void dfs(int u, int fa)
{
	for(int i = h[u]; ~i; i = ne[i])
	{
		int son = e[i];
		if(son == fa) continue;
		dfs(son, u);
		for(int j = m; j >= 0; j --)
			for(int k = 0; k <= j; k ++)
				f[u][j] = max(f[u][j], f[u][j-k] + f[son][k] + val);
	}
}

有依赖的背包

void dfs(int u, int fa)
{
	for(int i = h[u]; ~i; i = ne[i])
	{
		int son = e[i];
		if(son == fa) continue;
		dfs(son, u);
		for(int j = m; j >= 0; j --)
			for(int k = 0; k <= j; k ++)
				f[u][j] = max(f[u][j], f[u][j-k] + f[son][k] + val);
	}
}

二叉苹果树

void dfs(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
    	int son = e[i];
        if(son == fa) continue;
        dfs(son, u);
        for(int j = m; j >= 1; j -- )
            for(int k = 0; k <= j - 1; k ++ )
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[son][k] + w[i]);
    }
}