#include "friend.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int dp[1005][2];
int a[200005];
vector<int> edges[1005];
void dfs(int u, int p){
dp[u][1] = a[u];
for(auto v : edges[u]){
if(v == p)continue;
dfs(v, u);
dp[u][0] += dp[v][1];
dp[u][1] = max(dp[u][1], dp[v][0]);
}
dp[u][1] = max(dp[u][1], dp[u][0]);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans=0;
for(int i=0;i<n;i++)a[i] = confidence[i];
if(n <= 15){
int mask = 0;
vector<int> friends[13];
for(int i=1;i<n;i++){
if(protocol[i] == 0){
friends[i].pb(host[i]);
friends[host[i]].pb(i);
}else {
for(auto x : friends[host[i]]){
friends[i].pb(x);
friends[x].pb(i);
}
if(protocol[i] == 2){
friends[i].pb(host[i]);
friends[host[i]].pb(i);
}
}
}
mask = 1;
while(mask < (1<<n)){
int cost = 0;
vector<bool> used(n);
for(int i=0;i<n;i++){
if(!((1<<i)&mask))continue;
bool ok = true;
for(auto x : friends[i])if(used[x])ok=false;
if(ok)cost += confidence[i], used[i] = true;
}
ans = max(cost, ans);
mask++;
}
}else if(protocol[1] == 1){
for(int i=0;i<n;i++)ans += confidence[i];
}else if(protocol[1] == 2){
for(int i=0;i<n;i++)ans = max(ans, confidence[i]);
}else {
for(int i=1;i<n;i++){
edges[i].pb(host[i]);
edges[host[i]].pb(i);
}
dfs(0, 0);
ans = max(dp[0][0], dp[0][1]);
}
return ans;
}
