#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
bool no0 = 1, no1 = 1, no2 = 1;
for (int i = 1; i < n; i++) {
if(protocol[i] == 0) no0 = false;
if(protocol[i] == 1) no1 = false;
if(protocol[i] == 2) no2 = false;
}
vector<vector<int>> adj(n);
for (int i = 1; i < n; i++) {
if(protocol[i] == 1 || protocol[i] == 2){
for (auto &j : adj[host[i]]) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
if(protocol[i] == 0 || protocol[i] == 2) {
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
}
if(no0 && no2){ // no edges
int res = 0;
for (int i = 0; i < n; i++) {
res += confidence[i];
}
return res;
}
if(no0 && no1){ // fully conected
int res = 0;
for (int i = 0; i < n; i++) {
res = max(res, confidence[i]);
}
return res;
}
if(no1 && no2){ // tree
vector<int> odp(n, 0);
vector<int> ndp(n, 0);
function<void(int, int)> dfs = [&](int a, int p){
odp[a] = confidence[a];
for (auto &b : adj[a]) {
if(b == p) continue;
dfs(b, a);
ndp[a] += max(odp[b], ndp[b]);
odp[a] += ndp[b];
}
};
dfs(0, 0);
return max(odp[0], ndp[0]);
}
if(n <= 15){ // brute force
int mx = 0;
for (int i = 0; i < (1 << n); i++) {
vector<bool> active(n, 0);
int res = 0;
bool bad = 0;
for (int j = 0; j < n; j++) {
if(i & (1 << j)){
active[j] = 1;
res += confidence[j];
}
}
for (int j = 0; j < n; j++) {
for (auto &k : adj[j]) {
if(active[j] && active[k]) bad = 1;
}
}
if(!bad) mx = max(mx, res);
}
return mx;
}
return -1;
}
