给定一棵 $n$ 阶树，每个结点拥有重量 $w_i$ 和价值 $v_i$，且选取某个结点必须选取该结点的父结点。

给定背包容量 $M$，问可以得到的最大价值。

考虑后序遍历结点并编号，设 $\text{dp}(i,j)$ 表示仅考虑后序遍历前 $i$ 个结点的容量为 $j$ 的背包的最大价值。

考虑新加入的第 $i$ 个结点，发现后序遍历前 $[i-sz_i+1,i]$ 个结点代表结点 $i$ 的子树。

分别考虑不选取第 $i$ 个结点和选取第 $i$ 个结点的情况，于是有状态转移方程

$$ \text{dp}(i,j)=\max(\text{dp}(i-sz_i,j),\text{dp}(i-1,j-w_i)+v_i) $$

void dfs(int u){
	sz[u]=1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].to;
		dfs(v);
		sz[u]+=sz[v];
	}
	dfs_t++;
	_for(i,0,w[u])
	dp[dfs_t][i]=dp[dfs_t-sz[u]][i];
	_for(i,w[u],MAXM)
	dp[dfs_t][i]=max(dp[dfs_t-1][i-w[u]]+v[u],dp[dfs_t-sz[u]][i]);
}

洛谷p1273

给定一棵以 $1$ 为根的 $n$ 阶有根树，树的每条边有费用 $f_i$，树的叶节点有价值 $v_i$。

选取若干条边的利润为所有可以通过选取边与根节点连通的叶节点的价值和减去所有选取边的费用和。

求利润非负时最多可以选取的边数。