#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
// Find out best sample
const int maxn = 1010;
typedef long long ll;
vector < int > adj[maxn];
int edges[maxn][maxn];
void add_edge(int v, int u)
{
adj[v].push_back(u);
adj[u].push_back(v);
edges[v][u] = edges[u][v] = 1;
}
vector < int > ord;
int used[maxn];
void bfs(int v)
{
queue < int > q;
used[v] = 1;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
ord.push_back(cur);
for (int u : adj[cur])
{
if (used[u] == 0)
{
if (used[cur] == 1)
used[u] = 2;
else
used[u] = 1;
q.push(u);
}
}
}
}
int con[maxn], dp[maxn][2];
void dfs(int v, int p)
{
dp[v][1] = con[v];
used[v] = 1;
for (int u : adj[v])
{
if (u == p)
continue;
dfs(u, v);
dp[v][0] += max(dp[u][0], dp[u][1]);
dp[v][1] += dp[u][0];
}
}
int findSample(int n,int confidence[],int host[],int protocol[])
{
bool only_my = true, only_we = true;
for (int i = 1; i < n; i ++)
{
if (protocol[i] != 1)
only_my = false;
if (protocol[i] != 2)
only_we = false;
}
for (int i = 0; i < n; i ++)
{
con[i] = confidence[i];
}
if (n <= 10)
{
for (int i = 1; i < n; i ++)
{
if (protocol[i] == 0)
{
add_edge(i, host[i]);
}
else if (protocol[i] == 1)
{
for (int u : adj[host[i]])
add_edge(u, i);
}
else
{
for (int u : adj[host[i]])
add_edge(u, i);
add_edge(i, host[i]);
}
}
ll ans = 0;
for (int mask = 0; mask < (1 << n); mask ++)
{
bool tf = true;
for (int bit1 = 0; bit1 < n; bit1 ++)
for (int bit2 = 0; bit2 < n; bit2 ++)
{
if ((mask & (1 << bit1)) > 0 && (mask & (1 << bit2)) > 0)
{
if (edges[bit1][bit2])
tf = false;
}
}
///cout << mask << " : " << tf << endl;
if (!tf)
continue;
ll cur = 0;
for (int i = 0; i < n; i ++)
if ((mask & (1 << i)) > 0)
cur += confidence[i];
ans = max(ans, cur);
}
return ans;
}
else if (only_my)
{
int ans = 0;
for (int i = 0; i < n; i ++)
ans += confidence[i];
return ans;
}
else if (only_we)
{
int ans = 0;
for (int i = 0; i < n; i ++)
ans = max(ans, confidence[i]);
return ans;
}
else
{
for (int i = 1; i < n; i ++)
{
if (protocol[i] == 0)
{
add_edge(i, host[i]);
}
else
{
assert(0);
}
/**if (protocol[i] == 2)
{
for (int u : adj[host[i]])
add_edge(u, i);
}*/
}
ll ans = 0;
for (int i = 0; i < n; i ++)
{
if (!used[i])
{
dfs(i, -1);
ans = ans + max(dp[i][0], dp[i][1]);
}
}
return ans;
}
}
