P5875 [IOI 2014] friend 朋友

**这是一道交互题**

我们建立了一个由编号为 $0,\cdots,n - 1$ 的 $n$ 个人组成的社交网络。网络中的有些对会成为朋友。如果 $x$ 号人成为 $y$ 号人的朋友，则 $y$ 号人同时也会成为 $x$ 号人的朋友。 这些人将通过 $n$ 个阶段加入这个网络，阶段也编号为 $0$ 至 $n−1$。第 $i$ 号人在第 $i$ 个阶段加入。在阶段 $0$，$0$ 号人加入网络并成为唯一的人。此后 $n - 1$ 个阶段的各个阶段，都有一个人会被主持人加入到网络中，而这个主持人可以是已在网络中的任何一个人。在阶段 $i$ 中（$1\le i\le n−1$），该阶段的主持人可以用如下三种方式之一把第 $i$ 号人加入到网络中： - IAmYourFriend：将第 $i$ 号人仅变成主持人的朋友。 - MyFriendsAreYourFriends：将第 $i$ 号人变成主持人当前的每一个朋友的朋友。 注意，这个方式不会将第 $i$ 号人变成主持人的朋友。 - WeAreYourFriends：将第 $i$ 号人变成主持人的朋友，同时也变成主持人当前的每一个朋友的朋友。 在建立此网络之后，我们想挑选一个调查的样本，也就是说要从网络中选择一组人。由于朋友之间通常拥有相似的兴趣，因此样本不应包含任何一对互为朋友的人。每个人都会有一个调查的可信度，表示为一个正整数，而我们想要找出一个可信度总和最大的样本。 ### 任务 给定各阶段的描述以及每个人的可信度值，请找出一个可信度总和最大的样本。你只需要实现函数 `findSample`。 * `findSample(n, confidence, host, protocol)` * $n$: 人数. * `confidence`: 大小为 $n$ 的数组；`confidence[i]` 表示第 $i$ 号人的可信度。 * `host`: 大小为 $n$ 的数组；`host[i]` 表示阶段 i 的主持人。 * `protocol`: 大小为 $n$ 的数组；`protocol[i]` 表示在阶段 （$0

以下为交互库的输入格式。 第 $1$ 行：一个正整数 $n$，为人数。 第 $2$ 行：共 $n$ 个整数 $\mathrm{confidence}[0],\ldots,\mathrm{confidence}[n-1]$. 第 $3$ 行：共 $2n-2$ 个整数 $\mathrm{host}[1],\mathrm{protocol}[1], \mathrm{host}[2], \mathrm{protocol}[2],\cdots, \mathrm{host}[n-1], \mathrm{protocol}[n-1]$。

本题只支持 C++ 系列语言。 你只能提交一个源文件实现上述的函数，其命名与接口需遵循下面的要求。**不需要添加额外的头文件**。 `int findSample(int n, int confidence[], int host[], int protocol[]);`

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le \mathrm{confidence}[i] \le 10^6$。 |**子任务**|**分值**|$n$|**可信度**|**采用的方式**| |:-:|:-:|:-:|:-:|:-:| |1|$11$|$n\leq 10$|$1\leq \mathrm{confidence}\leq 10^6$|全部三种方式| |2|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `MyFriendsAreYourFriends`| |3|$8$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `WeAreYourFriends`| |4|$19$|$n\leq 1000$|$1\leq \mathrm{confidence}\leq 10^6$|只有 `IAmYourFriend`| |5|$23$|$n\leq 1000$|所有可信度值均为 $1$|只有 `MyFriendsAreYourFriends` 和 `IAmYourFriend` 两种方式| |6|$31$|$n\leq 10^5$|$1\leq \mathrm{confidence}\leq 10^4$|全部三种方式|