#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
struct UnionFind{
vector<int> par;
UnionFind(int n){
par.resize(n);
iota(par.begin(),par.end(),0);
}
int find(int i){
if(par[i] == i) return i;
return par[i] = find(par[i]);
}
void unite(int i, int j){
i = find(i);
j = find(j);
par[i] = j;
}
};
vector<int> arr,dpT, dpN;
vector<vector<int>> adj;
void DFS(int v){
dpT[v] = arr[v];
int oth1 = 0;
for(auto u : adj[v]){
DFS(u);
dpT[v] += dpN[u];
dpN[v] += dpT[u];
}
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans=0;
vector<vector<bool>> adj(n, vector<bool>(n));
for(int i = 1; i < n; i++){
if(protocol[i] == 0){
adj[host[i]][i] = true;
adj[i][host[i]] = true;
}else if(protocol[i] == 1){
for(int u = 0; u < n; u++){
if(adj[host[i]][u]){
adj[u][i] = true;
adj[i][u] = true;
}
}
}else{
adj[host[i]][i] = true;
adj[i][host[i]] = true;
for(int u = 0; u < n; u++){
if(adj[host[i]][u]){
adj[u][i] = true;
adj[i][u] = true;
}
}
}
}
int p2 = 1 << n;
for(int m = 0; m < p2; m++){
int val = 0;
for(int i = 0; i < n; i++){
if(m & (1 << i)){
val += confidence[i];
}
}
bool valid = true;
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
int a = (m & (1 << i));
int b = (m & (1 << j));
if(a && b){
if(adj[i][j]){
valid = false;
break;
}
}
}
if(!valid) break;
}
if(valid){
ans = max(ans, val);
}
}
return ans;
}
