P1060云止聆佳响（echo）

【题目背景】

龙韧于刚，龙吟激荡，云止聆佳响。

【题目描述】

群山的主脉与支脉层层伸展，远望如同一条卧于云间的龙脊。山脊上共有 $n$ 座听音台，其中 $1$ 号听音台位于山口。其余每座听音台都由一条山路与更靠近山口的听音台相连，这些山路使任意两座听音台之间都能互相到达。也就是说，它们构成一棵以 $1$ 号听音台为根的树。

第 $u$ 座听音台封存着一声音高为 $a_u$ 的龙吟。将这座听音台唤醒时，它能够为群山中的声音增添 $w_u$ 的吟响值。

为了让沉寂的龙吟重新贯穿群山，你需要沿着一条从山口向龙脊深处延伸的道路，依次唤醒若干座听音台 $p_1,p_2,\ldots,p_s$。对于每个 $1\leq i<s$，从山口前往 $p_{i+1}$ 时必须经过 $p_i$。换言之，$p_i$ 是 $p_{i+1}$ 的祖先。被唤醒的听音台不必在山路上直接相邻，但必须依次位于同一条道路上。

依次唤醒的听音台共同奏成一段龙吟。为了使每一声音都能清晰传向云间，要求龙吟中任意相邻两座听音台的音高不同。

对于一段龙吟中相邻的两座听音台：

• 若 $a_{p_i}<a_{p_{i+1}}$，称此处的龙吟正在上扬。
• 若 $a_{p_i}>a_{p_{i+1}}$，称此处的龙吟正在低回。

当连续两处的龙吟一处上扬、另一处低回时，龙吟会在它们之间发生一次激荡。也就是说，对于 $2\leq i<s$，当

时，龙吟在 $p_i$ 处发生一次激荡。

只唤醒一座听音台也能奏成一段合法的龙吟，此时不会发生激荡。

一段龙吟的吟响值为其中所有听音台贡献的吟响值之和。你需要在发生激荡的次数不超过 $k$ 的所有非空龙吟中，求出吟响值的最大值。

【输入格式】

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

本题包含多组测试数据。

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

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

第一行包含两个整数 $n,k$，分别表示听音台的数量与允许发生激荡的最大次数。

第二行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$。对于每个 $2\leq u\leq n$，$p_u$ 表示从听音台 $u$ 前往山口时经过的第一座听音台。

第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每座听音台记录的音高。

第四行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，表示每座听音台贡献的吟响值。

【输出格式】

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

对于每组测试数据，输出一行一个整数，表示满足要求的龙吟的最大吟响值。

【样例 1 输入】

10 226 131 1 2 2 344 2 7 6 1 553 5 4 6 7 865 071 2 3 483 1 4 2 592 8 4 7 3

【样例 1 输出】

115218

【说明/提示】

【样例 1 解释】

对于第一组测试数据，可以依次唤醒听音台 $1,2,5$。对应的音高依次为 $4,2,1$，龙吟始终低回，没有发生激荡，得到的吟响值为 $3+5+7=15$。

也可以依次唤醒听音台 $1,3,6$。对应的音高依次为 $4,7,5$，龙吟发生一次激荡，得到的吟响值为 $3+4+8=15$。可以证明不存在吟响值更大的合法龙吟。

对于第二组测试数据，不允许发生激荡。依次唤醒听音台 $2,4,5$ 时，音高依次为 $1,2,5$，得到的吟响值为 $8+7+3=18$，这是能够得到的最大值。

【样例 2】

见选手目录下的 $\textbf{\textit{echo/echo2.in}}$ 与 $\textbf{\textit{echo/echo2.ans}}$。

该组样例符合测试点 $1\sim 3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{echo/echo3.in}}$ 与 $\textbf{\textit{echo/echo3.ans}}$。

该组样例符合测试点 $4\sim 7$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{echo/echo4.in}}$ 与 $\textbf{\textit{echo/echo4.ans}}$。

该组样例符合测试点 $8\sim 11$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{echo/echo5.in}}$ 与 $\textbf{\textit{echo/echo5.ans}}$。

该组样例符合测试点 $12\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{echo/echo6.in}}$ 与 $\textbf{\textit{echo/echo6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n\leq 2\times 10^5$，$0\leq k\leq 8$，$1\leq a_u,w_u\leq 10^9$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$。

特殊性质 A：所有听音台构成一条以 $1$ 号听音台为一端的链。

特殊性质 B：$k=0$。