#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
bool subtask[6];
int G[20][20];
void add_edge(int a, int b) {
G[a][b] = 1;
G[b][a] = 1;
//~ cout << a << " " << b << endl;
}
vector<int> c;
int dp[1007][2];
vector<int> ch[1007];
vector<int> GG[1007];
int match[1007];
int clr[1007];
int viscnt;
int vis[1007];
void dfs(int w) {
dp[w][1] = c[w];
for(int u : ch[w]) {
dfs(u);
dp[w][0] += max(dp[u][0], dp[u][1]);
dp[w][1] += dp[u][0];
}
}
void add_edge2(int a, int b) {
GG[a].push_back(b);
GG[b].push_back(a);
//~ cout << a << " " << b << endl;
}
int dfs2(int w) {
if(vis[w] == viscnt)
return 0;
vis[w] = viscnt;
for(int u : GG[w]) {
if(match[u] == -1 || dfs2(match[u])) {
match[w] = u;
match[u] = w;
return 1;
}
}
return 0;
}
int findSample(int n,int confidence[],int host[],int protocol[]) {
for(int i = 1 ; i<= 5 ; i++)
subtask[i] = 1;
if(n > 10)
subtask[1] = 0;
for(int i = 1 ; i < n ; i++) {
if(protocol[i] == 0)
subtask[2] = subtask[3] = 0;
if(protocol[i] == 1)
subtask[3] = subtask[4] = 0;
if(protocol[i] == 2)
subtask[2] = subtask[4] = subtask[5] = 0;
}
if(subtask[1]) {
for(int i = 1 ; i < n ; i++) {
if(protocol[i] == 0) {
add_edge(i, host[i]);
} else if(protocol[i] == 1) {
for(int x = 0 ; x < n ; x++)
if(G[host[i]][x])
add_edge(x, i);
} else {
for(int x = 0 ; x < n ; x++)
if(G[host[i]][x])
add_edge(x, i);
add_edge(i, host[i]);
}
}
int res = 0;
for(int mask = 0 ; mask < (1 << n) ; mask++) {
int sum = 0;
bool ok = true;
for(int i = 0 ; i < n ; i++) {
if(mask & (1 << i)) {
sum += confidence[i];
for(int j = i + 1 ; j < n ; j++) {
if(mask & (1 << j)) {
if(G[i][j])
ok = false;
}
}
}
}
if(ok)
res = max(res, sum);
}
return res;
}
if(subtask[2]) {
int sum = 0;
for(int i = 0 ; i < n ; i++)
sum += confidence[i];
return sum;
}
if(subtask[3]) {
int maxv = 0;
for(int i = 0 ; i < n ; i++)
maxv = max(maxv, confidence[i]);
return maxv;
}
if(subtask[4]) {
c.resize(n);
for(int i = 0 ; i < n ; i++)
c[i] = confidence[i];
for(int i = 1 ; i < n ; i++)
ch[host[i]].push_back(i);
dfs(0);
return max(dp[0][0], dp[0][1]);
}
if(subtask[5]) {
memset(match, -1, sizeof match);
for(int i = 1 ; i < n ; i++) {
if(protocol[i] == 0) {
clr[i] = (1 - clr[host[i]]);
add_edge2(i, host[i]);
} else {
clr[i] = clr[host[i]];
for(int x : GG[host[i]])
add_edge2(i, x);
}
}
int cnt = 0;
for(int i = 0 ; i < n ; i++) {
if(!clr[i]) {
viscnt++;
cnt += dfs2(i);
}
//~ cout << i << " " << clr[i] << " " << match[i] << " " << cnt << endl;
}
return n - cnt;
}
return -1;
}
