Problem: jacks_candy_shop (2018 round2)

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 _i_th of which (1-indexed)
contains the single integer **Pi**.

### Output

For the _i_th 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



Code: // Jack's Candy Shop
// Solution by Adel Aly

#include <algorithm>
#include <vector>
#include <queue>
#include <cstdlib>
#include <iostream>
#include <ctime>

using namespace std;

const int MAXN = 2e5 + 10;
const int MAXM = 1e6 + 10;

int cands[MAXN], qIdx[MAXN];
long long ans;
priority_queue<int> Q[MAXN];
vector<int> adj[MAXN];

void solve(int n) {
  int myIdx = n, otherIdx;
  if (adj[n].size() > 0) {
    solve(adj[n][0]);
    myIdx = qIdx[adj[n][0]];
    for (int j = 1; j < adj[n].size(); ++j) {
      solve(adj[n][j]);
      otherIdx = qIdx[adj[n][j]];
      if (Q[otherIdx].size() > Q[myIdx].size()) {
        swap(otherIdx, myIdx);
      }

      while (!Q[otherIdx].empty()) {
        Q[myIdx].push(Q[otherIdx].top());
        Q[otherIdx].pop();
      }
    }
  }
  qIdx[n] = myIdx;
  Q[myIdx].push(n);
  while ((cands[n]--) && (!Q[myIdx].empty())) {
    ans += Q[myIdx].top();
    Q[myIdx].pop();
  }
}

int main() {
  int T, N, M, A, B, p;
  cin >> T;

  for (int tt = 1; tt <= T; ++tt) {
    ans = 0;
    cin >> N >> M >> A >> B;
    memset(cands, 0, MAXN * sizeof(int));
    ans = 0;
    for (int i = 0; i < N; i++) {
      adj[i].clear();
      while (!Q[i].empty()) {
        Q[i].pop();
      }
    }
    for (int i = 1; i < N; i++) {
      cin >> p;
      adj[p].push_back(i);
    }
    for (int i = 0; i < M; i++) {
      long long x = (1LL * A * i + B) % N;
      ++cands[x];
    }
    solve(0);
    cout << "Case #" << tt << ": " << ans << endl;
  }
  return (0);
}