题目背景

这是一道交互题

题目描述

我们建立了一个由编号为 $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<i<n$） 所采用的方式的代码: 0 代表 IAmYourFriend，1 代表 MyFriendsAreYourFriends，而 2 代表 WeAreYourFriends。
  • 由于在阶段 0 中没有主持人，因此 host[0] 和 protocol[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[]);

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

35

提示

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le \mathrm{confidence}[i] \le 10^6$。