g6-07617. 依赖选择·最优方案数

题目描述

给定一棵以 $1$ 为根的有根树，每个结点有正权 $w_{i}$ 。选择若干结点，满足选了孩子必须选父亲，且所选点数不超过 $m$ 。求权值和的最大值，以及取得最大值的方案数（对 $1 0^{9} + 7$ 取模）。

方案指结点集合；可以一个都不选（权值和 $0$ ）。

第一行两个整数 $n, m$ 。

第二行 $n$ 个整数 $w_{1}, \dots, w_{n}$ 。

第三行 $n - 1$ 个整数 $f_{2}, \dots, f_{n}$ 。

输入：

3 2
5 3 4
1 1

输出：

9 1

不超过 $2$ 个点：可选 ${1, 3}$ 得 $9$ （最优），方案数 $1$ 。