P1051树的价值（tree）

【题目描述】

给定一棵 $n$ 个结点的有根树，其中结点 $1$ 为根，结点 $i$（$2\leq i\leq n$）的父亲结点为结点 $p_i$。

对于 $1\leq i\leq n$，定义结点 $i$ 的深度 $d_i$ 为结点 $1$ 到结点 $i$ 的简单路径的边数。也就是说，$d_1=0$，$d_i=d_{p_i}+1$（$2\leq i\leq n$）。定义有根树的高度 $h$ 为所有结点深度的最大值，即 $h=\max_{i=1}^{n}d_i$。

给定高度的上界 $m$。在本题中，给定的有根树的高度不超过 $m$。

每个结点 $u$ 有一个整数权值 $a_u$。另外，给定一个长度为 $n$ 的整数序列 $b_1,b_2,\ldots,b_n$，其中 $b_j$ 表示长度为 $j$ 的链对应的价值系数。权值 $a_u$ 与价值系数 $b_j$ 均可能为负数。

若一个结点没有儿子，则称这个结点为叶子。设树中共有 $k$ 个叶子。小 X 会选择一个由所有叶子组成的排列 $q_1,q_2,\ldots,q_k$，并按照这个顺序依次探索这些叶子。这个排列称为一个探索序列。

当小 X 探索叶子 $q_i$ 时，会观察从根到 $q_i$ 的简单路径，并取出这条路径上此前从未被探索过的所有结点，记这些结点组成的集合为 $S_i$。此前已经探索过的所有根到叶路径构成一棵包含根的连通子树，因此 $S_i$ 中的结点一定构成一条连续的、从上向下的链，称为第 $i$ 次探索的新探索链。

令 $t_i$ 表示 $S_i$ 中深度最小的结点，$l_i=|S_i|$ 表示这条新探索链的长度。定义第 $i$ 次探索产生的探索价值为 $a_{t_i}b_{l_i}$，并定义这个探索序列的总价值为

定义这棵树的价值为所有探索序列的总价值的最大值。

你需要求出给定有根树的价值。

【输入格式】

本题包含多组测试数据。

从文件 $\textbf{\textit{tree.in}}$ 中读入数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含两个正整数 $n,m$，分别表示结点数量与高度的上界。

第二行包含 $n-1$ 个正整数 $p_2,p_3,\ldots,p_n$，分别表示每个结点的父亲结点。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，分别表示每个结点的权值。

第四行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，分别表示不同链长对应的价值系数。

【输出格式】

输出到文件 $\textbf{\textit{tree.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示给定有根树的价值。

【样例 1 输入】

10 225 231 1 2 243 -2 4 5 152 -1 3 0 064 371 2 38-3 2 -1 597 0 2 -4

【样例 1 输出】

127212

【说明/提示】

【样例 1 解释】

对于第一组测试数据，树中的叶子为结点 $3,4,5$。

小 X 可以选择探索序列 $5,3,4$。第一次探索叶子 $5$ 时，$S_1=\{1,2,5\}$，产生的探索价值为 $a_1b_3=3\times3=9$。第二次探索叶子 $3$ 时，$S_2=\{3\}$，产生的探索价值为 $a_3b_1=4\times2=8$。第三次探索叶子 $4$ 时，$S_3=\{4\}$，产生的探索价值为 $a_4b_1=5\times2=10$。

这个探索序列的总价值为 $9+8+10=27$。可以证明，不存在总价值更大的探索序列，因此这棵树的价值为 $27$。

对于第二组测试数据，结点 $4$ 是唯一的叶子。唯一的探索序列为 $4$，此时 $S_1=\{1,2,3,4\}$，产生的探索价值为 $a_1b_4=(-3)\times(-4)=12$，因此这棵树的价值为 $12$。

【样例 2】

见选手目录下的 $\textbf{\textit{tree/tree2.in}}$ 和 $\textbf{\textit{tree/tree2.ans}}$。

该附加样例满足测试点 $3,4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{tree/tree3.in}}$ 和 $\textbf{\textit{tree/tree3.ans}}$。

该附加样例满足测试点 $13,14$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{tree/tree4.in}}$ 和 $\textbf{\textit{tree/tree4.ans}}$。

该附加样例满足测试点 $18,19$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{tree/tree5.in}}$ 和 $\textbf{\textit{tree/tree5.ans}}$。

该附加样例满足测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于所有测试数据，保证：

• $0\leq c\leq25$，$1\leq T\leq5$。
• $2\leq n\leq8\times10^3$，$1\leq m\leq\min(n-1,800)$。
• 对于所有 $2\leq i\leq n$，均有 $1\leq p_i\leq i-1$。
• 给定的有根树的高度不超过 $m$。
• 对于所有 $1\leq i\leq n$，均有 $-10^6\leq a_i,b_i\leq10^6$。