g6-07510. 多组询问的依赖选择 未做

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点，结点 $i$ 有权值 $w_i$。

选择若干结点：若选了结点 $i$（$i\ne 1$），必须同时选它的父亲。

给出 $q$ 组询问，每组询问一个整数 $m$，求「所选结点数不超过 $m$」时权值和的最大值。

第一行两个整数 $n$ 与 $q$。

第二行 $n$ 个整数 $w_1,w_2,\dots ,w_n$。

第三行 $n-1$ 个整数 $f_2,f_3,\dots ,f_n$（$n=1$ 时该行为空）。

第四行 $q$ 个整数，依次为各组询问的 $m$。

一行 $q$ 个整数，空格分隔，依次为各组询问的答案。

输入：

4 3
5 -2 3 4
1 2 2
1 2 4

输出：

5 5 10

树为 $1$ 下挂 $2$，$2$ 下挂 $3,4$。$m=1$ 时选 $\{1\}$ 得 $5$；$m=2$ 时选 $\{1,2\}$ 得 $3$，不如 $5$，答案仍是 $5$；$m=4$ 时全选得 $10$。

• 对于 $30\%$ 的测试点，$1\le n\le 20$；
• 对于 $60\%$ 的测试点，$1\le n\le 200$；
• 对于全部测试点，$1\le n\le 1000$，$1\le q\le 10^5$，$|w_i|\le 10^4$，$1\le m\le n$。