g6-09076. 合并的代价账本 未做

给一棵以 $1$ 为根、共 $n$ 个结点的有根树，以及一个容量 $m$。树形背包在把孩子的子树合并进来时，每一步都要付出代价。请你按下面的规则把整棵树的合并代价记成一本账：

1. 从叶子开始，按后序处理每个结点 $u$（它的所有孩子都先处理完）；
2. $u$ 起初的已合并集合只有自己，记当前大小 $a=1$；
3. 把 $u$ 的孩子按编号从小到大依次合并：合并孩子 $v$ 时（$v$ 的整棵子树此刻已合并成一个大小为 $sz(v)$ 的整体），本次代价为 $\min (a,m)\times \min (sz(v),m)$；记账后 $a\leftarrow a+sz(v)$。

整棵树处理完后，输出账本上的总代价。

第一行两个整数 $n,m$，分别表示结点数与容量。

接下来 $n-1$ 行：第 $i$ 行一个整数 $f_i$（$2\le i\le n$），表示结点 $i$ 的父结点。

一行一个整数，表示全树合并的总代价。

• $1\le n\le 2000$
• $1\le m\le 1000$
• $1\le f_i<i$

合并代价：把大小为 $a$ 与 $b$ 的两个集合合并、元素两两配对处理，代价正比于 $a\times b$——树形背包把这一步记作合并孩子 $v$ 的转移代价 $O({sz}_u\times {sz}_v)$。容量 $m$ 相当于背包的容量上限：账本里每个因子都被截在 $m$ 以内，这与背包数组第二维只开到 $m$ 是同一件事。

一个漂亮的对照：如果完全不截断，整本账恰好等于 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$——因为每一对点只在它们的最近公共祖先处合并一次，$n$ 个点两两配对正好这么多对。截断只会让账变小。也正因为截断，先合并哪个孩子会改变中间的 $a$、从而记出不同的账，所以本题规定孩子按编号从小到大合并，答案唯一。