29799번 - Evolutionary Algorithms 서브태스크다국어

문제

Ada is working on a science project for school. She is studying evolution and she would like to compare how different species of organisms would perform when trying to solve a coding competition problem.

The $\mathbf{N}$ species are numbered with integers between 1ドル$ and $\mathbf{N},ドル inclusive. Species 1ドル$ has no direct ancestor, and all other species have exactly one direct ancestor each, from which they directly evolved. A (not necessarily direct) ancestor of species $x$ is any other species $y$ such that $y$ can be reached from $x$ by moving one or more times to a species direct ancestor starting from $x$. In this way, species 1ドル$ is a (direct or indirect) ancestor of every other species.

Through complex genetic simulations, she calculated the average score each of the $\mathbf{N}$ species would get in a particular coding competition. $\mathbf{S_i}$ is that average score for species $i$.

Ada is looking for interesting triplets to showcase in her presentation. An interesting triplet is defined as an ordered triplet of distinct species $(a, b, c)$ such that:

1. Species $b$ is a (direct or indirect) ancestor of species $a$.
2. Species $b$ is not a (direct or indirect) ancestor of species $c$.
3. Species $b$ has an average score strictly more than $\mathbf{K}$ times higher than both of those of $a$ and $c$. That is, $\mathbf{S_b} \ge \mathbf{K} \times \max(\mathbf{S_a}, \mathbf{S_c}) + 1$.

Given the species scores and ancestry relationships, help Ada by writing a program to count the total number of interesting triplets.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains two integers $\mathbf{N}$ and $\mathbf{K},ドル denoting the number of species and the factor which determines interesting triplets, respectively.

The second line of each test case contains $\mathbf{N}$ integers $\mathbf{S_1}, \mathbf{S_2}, \dots, \mathbf{S_N},ドル where $\mathbf{S_i}$ denotes the average score of species $i$.

The third line of each test case contains $\mathbf{N}-1$ integers $\mathbf{P_2}, \mathbf{P_3}, \dots, \mathbf{P_N},ドル meaning species $\mathbf{P_i}$ is the direct ancestor of species $i$.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the total number of interesting triplets according to Ada's definition.

제한

• 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.

Test Set 1 (7점)

• 3ドル \le \mathbf{N} \le 1000$.

Test Set 2 (16점)

For at most 30 cases:

• 3ドル \le \mathbf{N} \le 2 \times 10^5$.

For the remaining cases:

• 3ドル \le \mathbf{N} \le 1000$.

힌트

In Sample Case #1, there is only one possible interesting triplet: $(5, 3, 4)$. Indeed, we can verify that:

1. Species $b = 3$ is an ancestor of species $a = 5$.
2. Species $b = 3$ is not an ancestor of species $c = 4$.
3. The score of species $b = 3$ is more than $\mathbf{K}$ times higher than the scores of both $a = 5$ and $c = 4$: 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)$