#include "friend.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1001;
int n;
//vi graph[MAX_N];
int graph[MAX_N][MAX_N];
int a[MAX_N];
pii Solve(vvi &tree, int node, int parent) {
int x = a[node], y = 0;
for (int neighbor : tree[node]) {
if (neighbor == parent) continue;
auto [x1, y1] = Solve(tree, neighbor, node);
x += y1, y += x1;
}
chkmax(x, y);
return {x, y};
}
int color[MAX_N];
void Dfs(int node, int c) {
color[node] = c;
for (int i = 0; i < n; i++) {
if (graph[node][i] && !color[i]) {
Dfs(i, 3 - c);
}
}
}
int findSample(int N, int confidence[], int host[], int protocol[]) {
n = N;
bool subtask2 = true, subtask3 = true, subtask4 = true;
for (int i = 0; i < n; i++) a[i] = confidence[i];
vvi tree(n);
for (int i = 1; i < n; i++) {
if (protocol[i] != 1) subtask2 = false;
if (protocol[i] != 2) subtask3 = false;
if (protocol[i]) subtask4 = false;
if (protocol[i]) {
for (int j = 0; j < n; j++) {
if (graph[host[i]][j]) {
graph[i][j] = graph[j][i] = 1;
}
}
}
if (protocol[i] != 1) {
tree[i].push_back(host[i]);
tree[host[i]].push_back(i);
graph[host[i]][i] = graph[i][host[i]] = 1;
}
}
if (subtask2) {
int s = 0;
for (int i = 0; i < n; i++) s += a[i];
return s;
}
if (subtask3) {
return *max_element(a, a + n);
}
if (subtask4) {
return Solve(tree, 0, -1).x;
}
if (*max_element(confidence, confidence + n) == 1) {
Dfs(0, 1);
int ans = 0;
for (int i = 0; i < n; i++) {
ans += color[i] == 1;
}
return max(ans, n - ans);
}
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
int mask = i;
vi v;
while (mask) {
v.push_back(__builtin_ctz(mask));
mask -= mask & (-mask);
}
bool b = true;
int curr = 0;
for (int i : v) {
for (int j : v) {
if (graph[i][j]) {
b = false;
break;
}
}
if (!b) break;
curr += confidence[i];
}
if (b) chkmax(ans, curr);
}
return ans;
}
