Evolutionary Algorithms

Ada is working on a science project for school. She is studying evolution and wants to compare how different species perform when solving a coding competition problem.

There are $\mathbf{N}$ species numbered from 1 to $\mathbf{N}$. Species 1 has no direct ancestor, and every other species has exactly one direct ancestor, from which it evolved. An ancestor of species $x$ (direct or indirect) is any other species $y$ that can be reached from $x$ by repeatedly moving to a direct ancestor. So species 1 is an ancestor of every other species.

Each species $i$ has an average score $\mathbf{S\_i}$ in a particular coding competition. Ada calculated these scores with genetic simulations.

An interesting triplet is an ordered triplet of distinct species $(a, b, c)$ such that:

1. Species $b$ is an ancestor of species $a$.
2. Species $b$ is not an ancestor of species $c$.
3. Species $b$ has an average score strictly more than $\mathbf{K}$ times higher than both $a$ and $c$, that is, $\mathbf{S\_b} \ge \mathbf{K} \times \max(\mathbf{S\_a}, \mathbf{S\_c}) + 1$.

Count the interesting triplets.

The first line contains $\mathbf{T}$, the number of test cases. Each test case is given as follows.

The first line contains two integers $\mathbf{N}$ and $\mathbf{K}$.

The second line contains $\mathbf{N}$ integers $\mathbf{S\_1}, \mathbf{S\_2}, \dots, \mathbf{S\_N}$.

The third line contains $\mathbf{N}-1$ integers $\mathbf{P\_2}, \mathbf{P\_3}, \dots, \mathbf{P\_N}$, where $\mathbf{P\_i}$ is the direct ancestor of species $i$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1, and $y$ is the total number of interesting triplets.

• $1 \le \mathbf{T} \le 100$.
• $1 \le \mathbf{K} \le 10^9$.
• $1 \le \mathbf{S\_i} \le 10^9$ for all $i$.
• $1 \le \mathbf{P\_i} \le \mathbf{N}$ for all $i$.
• Species 1 is a (direct or indirect) ancestor of all other species.

In Sample Case #1, the only interesting triplet is $(5, 3, 4)$. Species 3 is an ancestor of species 5, and it is not an ancestor of species 4. Also, $6 = \mathbf{S\_3} \ge \mathbf{K} \times \max(\mathbf{S\_4}, \mathbf{S\_5}) + 1 = 2 \times \max(2, 2) + 1 = 5$.

In Sample Case #2, there are seven interesting triplets:

• $(4, 3, 1)$
• $(4, 3, 6)$
• $(4, 7, 1)$
• $(4, 7, 5)$
• $(4, 7, 6)$
• $(5, 3, 1)$
• $(5, 3, 6)$