Description

We build a social network consisting of $n$ people numbered $0,\cdots,n - 1$. Some pairs of people in the network will become friends. If person $x$ becomes a friend of person $y$, then person $y$ will also become a friend of person $x$.

These people will join the network in $n$ stages, also numbered from $0$ to $n-1$. Person $i$ joins in stage $i$. In stage $0$, person $0$ joins the network and is the only person. After that, in each of the remaining $n - 1$ stages, one person will be added to the network by a host, and this host can be any person already in the network. In stage $i$ ($1\le i\le n−1$), the host can add person $i$ to the network using one of the following three methods:

• IAmYourFriend: Make person $i$ become friends only with the host.
• MyFriendsAreYourFriends: Make person $i$ become friends with each of the host's current friends. Note that this method does not make person $i$ become friends with the host.
• WeAreYourFriends: Make person $i$ become friends with the host, and also become friends with each of the host's current friends.

After building the network, we want to choose a survey sample, that is, select a group of people from the network. Since friends usually have similar interests, the sample should not contain any pair of people who are friends with each other. Each person has a survey credibility value, given as a positive integer, and we want to find a sample with the maximum total credibility.

Task

Given the description of each stage and the credibility value of each person, find a sample with the maximum total credibility. You only need to implement the function findSample.

• findSample(n, confidence, host, protocol)
  • $n$: the number of people.
  • confidence: an array of size $n$; confidence[i] is the credibility of person $i$.
  • host: an array of size $n$; host[i] is the host of stage $i$.
  • protocol: an array of size $n$; protocol[i] is the code of the method used in stage ($0<i<n$): 0 means IAmYourFriend, 1 means MyFriendsAreYourFriends, and 2 means WeAreYourFriends.
  • Since there is no host in stage 0, host[0] and protocol[0] are undefined, and your program must not access them.

This function should return the maximum possible total credibility of the sample.

Input Format

Below is the input format for the interactive library.

Line $1$: a positive integer $n$, the number of people.

Line $2$: $n$ integers $\mathrm{confidence}[0],\ldots,\mathrm{confidence}[n-1]$.

Line $3$: $2n-2$ integers $\mathrm{host}[1],\mathrm{protocol}[1], \mathrm{host}[2], \mathrm{protocol}[2],\cdots, \mathrm{host}[n-1], \mathrm{protocol}[n-1]$.

Output Format

This problem only supports the C++ language series.

You can only submit one source file implementing the function above. The name and interface must follow the requirements below. Do not add extra header files.

int findSample(int n, int confidence[], int host[], int protocol[]);

6
13 3 6 20 10 15
0 0 0 1 1 2 2 1 0 0

35

Hint

For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le \mathrm{confidence}[i] \le 10^6$.

Translated by ChatGPT 5