#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int N = 1000 + 5;
int dp[N][2], ans, onecnt, zerocnt;
vector<int> graph[N];
bool vis[N];
void gengraph(int n, int host[], int protocol[]){
for(int i = 1; i < n; i++){
if(protocol[i] != 0){
for(auto e : graph[host[i]]){
graph[e].push_back(i);
graph[i].push_back(e);
}
}
if(protocol[i] != 1){
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
}
}
void dfs(int v, int confidence[]){
vis[v] = true;
dp[v][1] = confidence[v];
for(auto e : graph[v]){
if(!vis[e]){
dfs(e, confidence);
dp[v][1] += dp[e][0];
dp[v][0] += max(dp[e][0], dp[e][1]);
}
}
}
void colorgraph(int v, int c){
vis[v] = true;
if(c == 1) onecnt++;
else zerocnt++;
for(auto e : graph[v]){
if(!vis[e]) colorgraph(e, c ^ 1);
}
}
int findSample(int n, int confidence[], int host[], int protocol[]){
if(n <= 10){ // Subtask 1
gengraph(n, host, protocol);
for(int m = 0; m < (1 << n); m++){
bool flag = true;
int curans = 0;
for(int i = 0; i < n; i++){
if(m & (1 << i)){
curans += confidence[i];
for(auto e : graph[i]){
if(m & (1 << e)) flag = false;
}
}
}
if(flag) ans = max(ans, curans);
}
return ans;
}
else if(count(protocol + 1, protocol + n, 1) == n - 1){ // Subtask 2
return accumulate(confidence, confidence + n, 0);
}
else if(count(protocol + 1, protocol + n, 2) == n - 1){ // Subtask 3
return *max_element(confidence, confidence + n);
}
else if(count(protocol + 1, protocol + n, 0) == n - 1){ // Subtask 4
gengraph(n, host, protocol);
for(int i = 0; i < n; i++){
if(!vis[i]){
dfs(i, protocol);
ans += max(dp[i][0], dp[i][1]);
}
}
return ans;
}
else if(count(protocol + 1, protocol + n, 2) == 0){ // Subtask 5
gengraph(n, host, protocol);
for(int i = 0; i < n; i++){
if(!vis[i]){
onecnt = zerocnt = 0;
colorgraph(i, 0);
ans += max(onecnt, zerocnt);
}
}
return ans;
}
else return -1;
}
