给你一棵由 $$$n$$$ 个顶点组成的有根树。顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。您还会获得一个分数数组 $$$s_1, s_2, \ldots, s_n$$$。
如果以下两个条件都为真,则 $$$k$$$ 简单路径的多重集被称为有效。
- 每条路径从 $$$1$$$ 开始。
- 设 $$$c_i$$$ 为覆盖顶点 $$$i$$$ 的路径数。对于具有相同父节点的每对顶点 $$$(u,v)$$$ ($$$2\le u,v\le n$$$),$$$|c_u-c_v|\le 1$$$ 成立。
可以证明,总是可以找到至少一个有效的多重集。找到所有有效多重集中的最大值。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个空格分隔的整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) 和 $$$k$$$ ($$$1 \le k \le 10^9$$$) — 树的大小和所需的路径数量。
第二行包含 $$$n - 1$$$ 以空格分隔的整数 $$$p_2,p_3,\ldots,p_n$$$ ($$$1\le p_i\le n$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 个顶点的父顶点。保证这个值描述一个有效的树,根为$$$1$$$。
第三行包含 $$$n$$$ 空格分隔的整数 $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \le s_i \le 10^4$$$) — 顶点的分数。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10 ^ 5$$$。
输出
对于每个测试用例,打印一个整数 - 路径多重集的最大值。
示例
输入 #1
2 5 4 1 2 1 3 6 2 1 5 7 5 3 1 2 1 3 6 6 1 4 10
输出 #1
54 56
注意
在第一个测试用例中,最佳解决方案之一是四个路径 $$$1 \to 2 \to 3 \to 5$$$、$$$1 \to 2 \to 3 \to 5$$$、$$$1 \to 4$$$、$$$1 \to 4$$$,这里 $$$c=[4,2,2,2,2]$$$。该值等于$$$4\cdot 6+ 2\cdot 2+2\cdot 1+2\cdot 5+2\cdot 7=54$$$。
在第二个测试用例中,最佳解决方案之一是三个路径$$$1 \to 2 \to 3 \to 5$$$,$$$1 \to 2 \to 3 \to 5$$$,$$$1 \to 4$$$,这里$$$c=[3,2,2,1,2]$$$。该值等于$$$3\cdot 6+ 2\cdot 6+2\cdot 1+1\cdot 4+2\cdot 10=56$$$。