9554: 溯源

小 hua 学习了树，并发现一个草履虫家族可以用树的结构很好的刻画。

有一个根节点称为草履虫祖宗（$1$ 号节点），之后会有若干后代，构成一个有根树的结构（每个草履虫有唯一的父亲 fufu）。

每个草履虫（节点）还有一个价值 auau。

小 hua 想把草履虫家族割裂，她可以选择删掉若干条树边（共 2n−12n−1 种方案），求其中合法的方案的权值和。

其中：

• 一个方案合法，当且仅当，每个连通块中，在原本树中构成直接祖先后代关系的草履虫的价值差 $\le k$。
• 一个方案的权值定义为，所有连通块大小的乘积。
• 称 $u,v$ 构成直接祖先后代关系，当且仅当 $u=f(f(...f(v)))$ 或 $v=f(f(...f(u)))$，题目即要求同一连通块中所有这样的 $u,v$ 均满足 ∣au−av∣≤k∣au−av∣≤k。

第一行一个正整数 $T$ 表示测试数据组数，对于之后的每组测试数据：

• 第一行两个正整数 $n,k$，表示树的节点个数和极差限制。
• 第二行 $n$ 个正整数表示各个点的点权。
• 第三行 $n-1$ 个正整数分别表示 f2,f3,⋯,fnf2,f3,⋯,fn，保证 fifi 小于 $i$。