oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

candyshop Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Jack is a little boy with big dreams: to own the biggest candy shop in the world! He's off to a modest start with N candies for sale, numbered from 0 to N - 1. The price of candy i is i dollars. In his shop's front window, Jack has arranged his candies in the shape of a tree rooted at candy 0, with the parent of each other candy i (1 ≤ i < N) being candy Pi.

M other kids in Jack's neighbourhood have agreed to come by and be his first customers! Jack has assigned them customer numbers from 0 to M - 1. Unfortunately, these kids are a bit picky when it comes to sweets. Customer i only likes candies within the subtree rooted at candy Ci. This means that they're only willing to purchase a candy if it's either candy Ci, or one of its children, or one of its childrens' children, and so on. They also have amazing self-restraint — each customer will limit themselves to buying at most one candy.

For each of the M customers, Jack may either sell them any single candy of his choice within the customer's required subtree, or no candy at all. Each of the N candies may be sold to at most one customer. Jack is willing to do whatever it takes to achieve his dreams, even if it means extorting as much cash as possible from fellow children. As such, he'd like to choose candies to sell such that the sum of their prices is maximized. Can you help him determine this maximum sum of candy prices?

In order to reduce the size of the input data, C0..M-1 may be generated as follows using given constants A and B:

Ci = (A * i + B) % N (for i = 0 .. M - 1)

Input

Input begins with an integer T, the number of trees. For each tree, there is first a line containing the space-separated integers N, M, A, and B. Then N - 1 lines follow, the ith of which (1-indexed) contains the single integer Pi.

Output

For the ith tree, output a line containing "Case #i: " followed by the maximum possible sum of prices of candies which Jack can sell.

Constraints

1 ≤ T ≤ 20
1 ≤ N ≤ 200,000
0 ≤ M ≤ 1,000,000
0 ≤ A, B, Pi, Ci < N
It is guaranteed that each test case describes a single valid tree rooted at candy 0.

Explanation of Sample

In the first case, C = [0]. The only customer can be sold any candy in candy 0's subtree, which includes candies 0 and 1. Jack should choose to sell them candy 1, which has a price of 1 dollar.
In the second case, C = [2, 0, 2]. Jack should sell candy 2 to customer 0, candy 3 to customer 1, and no candy to customer 2. The sum of these candy prices is 2 + 3 = 5 dollars.
In the third case, C = [4, 6, 0, 2].

Sample Input

4
2 1 1 0
0
4 3 2 2
3
0
0
8 4 2 4
0
1
0
0
7
1
4
20 14 6 6
5
4
8
0
2
11
18
4
4
11
4
5
6
8
13
3
6
5
15

Sample Output

Case #1: 1
Case #2: 5
Case #3: 20
Case #4: 165

Tags

Graph Theory, Data Structure, Set Merging

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o candyshop -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.