Igor Perić

Problem

Wile lives alone in the desert, so he entertains himself by building complicated machines that run on chain reactions. Each machine consists of N modules indexed 1,2,…,N. Each module may point at one other module with a lower index. If not, it points at the abyss.

Modules that are not pointed at by any others are called initiators. Wile can manually trigger initiators. When a module is triggered, it triggers the module it is pointing at (if any) which in turn may trigger a third module (if it points at one), and so on, until the chain would hit the abyss or an already triggered module. This is called a chain reaction.

Each of the N modules has a fun factor Fi. The fun Wile gets from a chain reaction is the largest fun factor of all modules that triggered in that chain reaction. Wile is going to trigger each initiator module once, in some order. The overall fun Wile gets from the session is the sum of the fun he gets from each chain reaction.

For example, suppose Wile has 4 modules with fun factors F1=60,F2=20,F3=40, and F4=50 and module 1 points at the abyss, modules 2 and 3 at module 1, and module 4 at module 2. There are two initiators (3 and 4) that Wile must trigger, in some order.

As seen above, if Wile manually triggers module 4 first, modules 4, 2, and 1 will get triggered in the same chain reaction, for a fun of max(50,20,60)=60. Then, when Wile triggers module 3, module 3 will get triggered alone (module 1 cannot get triggered again), for a fun of 40, and an overall fun for the session of 60+40=100.

However, if Wile manually triggers module 3 first, modules 3 and 1 will get triggered in the same chain reaction, for a fun of max(40,60)=60. Then, when Wile triggers module 4, modules 4 and 2 will get triggered in the same chain reaction, for a fun of max(50,20)=50, and an overall fun for the session of 60+50=110.

Given the fun factors and the setup of the modules, compute the maximum fun Wile can get if he triggers the initiators in the best possible order.

Input

The first line of the input gives the number of test cases, T. T test cases follow, each described using 3 lines. Each test case starts with a line with a single integer N, the number of modules Wile has. The second line contains N integers F1,F2,…,FN where Fi is the fun factor of the i-th module. The third line contains NN integers P1,P2,…PN. If Pi=0, that means module i points at the abyss. Otherwise, module i points at module Pi.

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 maximum fun Wile can have by manually triggering the initiators in the best possible order.

Limits

Memory limit: 1 GB.
1≤T≤100
1≤Fi≤10^9
0≤Pi≤i−1, for all i

Test Set 1 (Visible Verdict)

Time limit: 5 seconds.
1≤N≤10

Test Set 2 (Visible Verdict)

Time limit: 5 seconds.
1≤N≤1000

Test Set 3 (Hidden Verdict)

Time limit: 10 seconds.
1≤N≤100000

Sample input

3
4
60 20 40 50
0 1 1 2
5
3 2 1 4 5
0 1 1 1 0
8
100 100 100 90 80 100 90 100
0 1 2 1 2 3 1 3

Sample output

Case #1: 110
Case #2: 14
Case #3: 490

Sample Case #1 is the one explained in the problem statement.

In Sample Case #2, there are 4 initiators (modules 2 through 5), so there are 4 chain reactions. Activating them in order 3,5,4,2 yields chains of fun 3,5,4,2 for an overall fun of 14. Notice that we are summing the four highest fun numbers in the input, so there is no way to get more than that.

In Sample Case #3, an optimal activation order of the 5 initiators is 4,5,7,6,8.

Solution

The solution is a variant of the Breadth First Search (BFS).

One observation is that decision which chain to trigger first depends only on the nodes with in-degree higher than 1 (multiple nodes are sinking into it). Once they are used, they interrupt all the other chains connecting to that common node. We can try to let all of the chains burn from the initiator nodes until they hit their common nodes, tracking the maximum fun factor along each of the chains. We denote this maximum fun factor along a burning chain with Pi, so we can refer to these currently pending chains which did not reach the abyss yet.

Now we must assign this common node with fun factor V to a single pending chain C out of all of the pending chains Pi. The key insight is that we want to pick C that maximises V – C, since that will contribute the most to the increase of the end sum. We do that by picking C to be the chain with the smallest fun factor among all of the pending chains Pi. After assigning node V to chain C, we connect all of the other pending chains pointing to V to abyss (they can’t continue burning further).

Implementation details

The first step is to find the initiator nodes by tracking the in-degree while reading the input. These nodes will be added to the traversal queue first.

While traversing the reaction graph we need to store each currently burning chain as a state. Our state for BFS will be a pair of current maximum fun factor for the burning chain, coupled with the index of the node in which we are currently positioned. A single burning chain will have exactly one state in the queue.

In each iteration we want to keep burning the chain with the smallest fun factor so far, so it “reaches” the common node before the other chains with the higher fun factor. One step of burning a single chain means moving onto the next node in the chain, which potentially updates the maximum fun factor for the current state (if the new node we are moving into has higher factor than the current max factor stored in the state).

Data structure suitable for maintaining a sorted list is priority queue. Complexity of adding an element is O(logN), removing an element is O(1) and finding a minimum is O(1). In each of the N iterations we will get the minimum, remove it from the queue and re-insert it after updating it’s index and fun factor, so the total complexity is O(N logN).

We will use a set of pairs from the STL as a priority queue.

#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>

using namespace std;

int main(){

    int t, k = 0;
    cin >> t;
    while (k++ < t) {

        cout << "Case #" << k << ": ";

        long n, i;
        cin >> n;
        vector<long> f(n, 0); // fun factor
        vector<long> c(n, 0); // connectivity graph
        vector<long> d(n, 0); // in-degree of the each node
        vector<bool> v(n, false); // visited masks
        for (i=0;i<n;i++) cin >> f[i];
        for (i=0;i<n;i++) {
            cin >> c[i];
            c[i]--;
            if (c[i] >= 0) d[ c[i] ]++; // increment in-degree
        }

        // queue will be pairs of current fun...
        // ... and the node we're currently in
        set< pair<long, long> > q;

        // find the initiator nodes
        for (i=0;i<n;i++) {
            if (d[i] == 0) {
                q.insert({ f[i], i });
                v[i] = true;
            }
        }

        long sol = 0;
        while (!q.empty()) {
            pair<long, long> current = *q.begin();
            q.erase(q.begin());
          
            // check if we reached the abyss
            if (c[current.second] == -1 || v[c[current.second]]) {
                sol += current.first;
                continue;
            }
            // move to the next node
            q.insert({ 
                max(current.first, f[ c[current.second] ]),
                c[current.second]
                });
            // mark the current node as used (connected to abyss)
            v[ c[current.second] ] = true;
        }
        cout << sol << endl;
    }
    return 0;
}