Page not loading? Try clicking here.
Placeholder

#10460

Evolutionary Algorithms 40s 2048MB

Problems

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.


Input

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.


Output

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.


Example 

2
5 2
3 3 6 2 2
3 1 1 3
7 3
2 4 7 2 2 1 8
6 1 7 3 1 3
Case #1: 1
Case #2: 7
In Sample Case #1, there is only one possible interesting triplet: (5, 3, 4). Indeed, we can verify that: - Species b = 3 is an ancestor of species a = 5. - Species b = 3 is not an ancestor of species c = 4. - 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)

Source

GCJ 2023c C

You must sign in to write code.