#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
int dp[1005][2],val[1005];
vector<int> adj[1005];
bool gg[1005][1005];
void dfs(int u){
for(auto v:adj[u]){
dfs(v);
dp[u][1] += dp[v][0];
dp[u][0] += dp[v][1];
}
dp[u][1] += val[u];
dp[u][1] = max(dp[u][1],dp[u][0]);
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int type0 = 0,type1 = 0,type2 = 0;
int ans = 0;
for(int i = 1; i < n; i ++){
type0 |= (protocol[i]==0);
type1 |= (protocol[i]==1);
type2 |= (protocol[i]==2);
}
if(type0 and (!type1) and (!type2)){
for(int i = 1; i < n; i ++){
val[i] = confidence[i];
adj[host[i]].push_back(i);
}
val[0] = confidence[0];
dfs(0);
ans = dp[0][1];
}
else if(type1 and (!type0) and (!type2)){
for(int i = 0; i < n; i ++) ans += confidence[i];
}
else if(type2 and (!type1) and (!type0)){
for(int i = 0; i < n; i ++) ans = max(ans,confidence[i]);
}
else{
for(int i = 1; i < n; i ++){
if(protocol[i] == 0){
gg[i][host[i]] = 1;
gg[host[i]][i] = 1;
}
else if(protocol[i] == 1){
for(int j = 0; j < n; j ++){
gg[i][j] = gg[host[i]][j];
gg[j][i] = gg[i][j];
}
}
else{
for(int j = 0; j < n; j ++){
gg[i][j] = gg[host[i]][j];
gg[j][i] = gg[i][j];
}
gg[i][host[i]] = 1;
gg[host[i]][i] = 1;
}
}
for(int i = 0; i < (1<<n); i ++){
vector<int> v;
int cur = 0;
for(int j = 0; j < n; j ++){
if((1<<j)&i){
v.push_back(j);
cur += confidence[j];
}
}
for(auto j1:v) for(auto j2:v) if(gg[j1][j2]) cur = 0;
ans = max(ans,cur);
}
}
return ans;
}
