#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
vector<int> adj[N];
// Find out best sample
int dp[N][2];
int* conf;
int n;
bool open[N];
int dfs(int node, int par)
{
dp[node][0] = 0;
dp[node][1] = conf[node];
for (int next : adj[node])
{
if (next == par) continue;
dfs(next, node);
dp[node][0] += max(dp[next][0], dp[next][1]);
dp[node][1] += dp[next][0];
}
return max(dp[node][0], dp[node][1]);
}
bool legal(int node)
{
for (int next : adj[node])
{
if (open[next]) return false;
}
return true;
}
int go(int i, int sum)
{
if (i == n)
{
bool ok = true;
for (int j = 0; j< n; j++) if (open[j])ok = ok && legal(j);
if (ok) return sum;
return 0;
}
int best = 0;
best = max(best, go(i + 1, sum));
open[i] = true;
best = max(best, go(i + 1, sum + conf[i]));
open[i] = false;
return best;
}
int findSample(int n1,int conf1[],int host[],int pro[]){
n = n1;
conf = conf1;
int ans=10;
int freq[3] = {};
for (int i = 1; i < n; i++) freq[pro[i]]++;
if (freq[0] == 0 && freq[2] == 0)
{
int sum = 0;
for (int i = 0; i < n; i++) sum += conf[i];
return sum;
} else if (freq[0] == 0 && freq[1] == 0)
{
int res = 0;
for (int i = 0; i < n; i++) res = max(res, conf[i]);
return res;
} else if (freq[1] == 0 && freq[2] == 0)
{
for (int i = 1; i < n; i++)
{
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
return dfs(0, -1);
} else if (n <= 10)
{
for (int i = 1; i < n; i++)
{
if (pro[i] == 0)
{
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
} else if (pro[i] == 1)
{
for (int j : adj[host[i]])
{
adj[i].push_back(j);
adj[j].push_back(i);
}
} else
{
for (int j : adj[host[i]])
{
adj[i].push_back(j);
adj[j].push_back(i);
}
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
}
return go(0, 0);
}
return ans;
}
