P5875 [IOI 2014] friend

**This is an interactive problem.**

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

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]$.

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[]);`

For $100\%$ of the testdata, $2 \le n \le 10^5$, $1 \le \mathrm{confidence}[i] \le 10^6$. |**Subtask**|**Score**|$n$|**Credibility**|**Method used**| |:-:|:-:|:-:|:-:|:-:| |1|$11$|$n\leq 10$|$1\leq \mathrm{confidence}\leq 10^6$|all three methods| |2|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|only `MyFriendsAreYourFriends`| |3|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|only `WeAreYourFriends`| |4|$19$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|only `IAmYourFriend`| |5|$23$|$n\leq 1000$|all credibility values are $1$|only `MyFriendsAreYourFriends` and `IAmYourFriend`| |6|$31$|$n\leq 10^5$|$1\leq \mathrm{confidence}\leq 10^4$|all three methods| Translated by ChatGPT 5