Maximum Weighted Independent Set in a Dynamic Social Network

We construct a social network consisting of n people numbered from \(0\) to \(n-1\). Some pairs of people become friends. The friendship relation is symmetric: if person \(x\) becomes a friend of person \(y\) then person \(y\) simultaneously becomes a friend of person \(x\).

The network is built in n stages, also numbered from \(0\) to \(n-1\); person \(i\) joins the network at stage \(i\). At stage \(0\), person \(0\) joins and is the only one in the network. In each subsequent stage \(i\) (\(1 \le i \le n-1\)), a host (who is any person who already joined the network) brings person \(i\) into the network by following one of three protocols:

• IAmYourFriend: only make person \(i\) a friend of the host.
• MyFriendsAreYourFriends: for each current friend \(f\) of the host, make person \(i\) a friend of \(f\). Note: this protocol does not make person \(i\) a friend of the host.
• WeAreYourFriends: combine the above two protocols; that is, make person \(i\) a friend of the host and also a friend of every friend \(f\) of the host.

After the network is built, we wish to select a survey sample – a set of people from the network – with the constraint that no two people in the sample are friends (i.e. the sample forms an independent set in the friendship graph). Each person \(i\) has a confidence value (a positive integer). The goal is to choose an independent set with the maximum total confidence sum.

Your task is to implement the function findSample that computes this maximum sum.

Function Signature: findSample(n, confidence, host, protocol)

Note: In stage \(0\), there is no host; hence, host[0] and protocol[0] are undefined and will not be accessed.

inputFormat

The input is given as follows:

1. An integer \(n\) representing the number of people.
2. \(n\) space‐separated positive integers representing the confidence values of persons \(0, 1, \ldots, n-1\).
3. \(n\) integers representing the host for each stage. For stage \(0\), a dummy value is provided (and will not be used). For \(i \ge 1\), host[i] is the host (an index in \([0, i-1]\)) used to introduce person \(i\).
4. \(n\) integers representing the protocol codes for each stage. For stage \(0\), a dummy value is provided (and will not be used). For \(i \ge 1\), protocol[i] is the code that indicates which protocol is used: 0 for IAmYourFriend, 1 for MyFriendsAreYourFriends, and 2 for WeAreYourFriends.

outputFormat

Output a single integer, the maximum total confidence sum of an independent set (i.e. a set of people in the network with no two of whom are friends).

sample

3
10 20 30
-1 0 1
-1 0 1

50