#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int solve_1(int n,int confidence[],int host[],int protocol[]){
vector<int>v[10];
for(int i=1;i<n;i++){
if(protocol[i]==0){
v[i].push_back(host[i]);
v[host[i]].push_back(i);
}
if(protocol[i]==1){
for(int j:v[host[i]]){
v[j].push_back(i);
v[i].push_back(j);
}
}
if(protocol[i]==2){
for(int j:v[host[i]]){
v[j].push_back(i);
v[i].push_back(j);
}
v[i].push_back(host[i]);
v[host[i]].push_back(i);
}
}
int res=0;
for(int i=0;i<(1<<n);i++){
bool b[10];
for(int j=0;j<n;j++){
b[j]=(i>>j)&1;
}
bool f=true;
int c=0;
for(int j=0;j<n;j++){
if(!b[j])continue;
c+=confidence[j];
for(int k:v[j]){
if(b[k])f=false;
}
}
if(f&&res<c)res=c;
}
return res;
}
int solve_2(int n,int confidence[],int host[],int protocol[]){
int res=0;
for(int i=0;i<n;i++){
res+=confidence[i];
}
return res;
}
int solve_3(int n,int confidence[],int host[],int protocol[]){
int res=0;
for(int i=0;i<n;i++){
if(res<confidence[i])res=confidence[i];
}
return res;
}
vector<int>v_4[1000];
int C_4[1000][2];
void dfs_4(int x,int from){
for(int i:v_4[x]){
if(i==from)continue;
dfs_4(i,x);
C_4[x][0]+=max(C_4[i][0],C_4[i][1]);
C_4[x][1]+=C_4[i][0];
}
}
int solve_4(int n,int confidence[],int host[],int protocol[]){
for(int i=1;i<n;i++){
v_4[i].push_back(host[i]);
v_4[host[i]].push_back(i);
}
for(int i=0;i<n;i++){
C_4[i][1]=confidence[i];
}
dfs_4(0,0);
return max(C_4[0][0],C_4[0][1]);
}
struct edge{
int to,cost,rev;
};
vector<edge>e_5[1002];
vector<int>v_5[1000];
bool vis_5[1000],bw_5[1000];
void dfs_5(int x,int from){
vis_5[x]=true;
for(int i:v_5[x]){
if(i==from)continue;
bw_5[i]=bw_5[x]^true;
dfs_5(i,x);
}
}
int dfs2_5(int n,int x,int cost){
if(x==n+1)return cost;
if(vis_5[x])return 0;
vis_5[x]=true;
for(edge &e:e_5[x]){
int k=dfs2_5(n,e.to,min(cost,e.cost));
if(k){
e.cost-=k;
e_5[e.to][e.rev].cost+=k;
return k;
}
}
return 0;
}
int calc_max_flow_5(int n){
int c=0;
while(true){
for(int i=0;i<n+2;i++){
vis_5[i]=false;
}
int k=dfs2_5(n,n,0xE869120);
if(!k)break;
c+=k;
}
return c;
}
int solve_5(int n,int confidence[],int host[],int protocol[]){
for(int i=1;i<n;i++){
if(protocol[i]==0){
v_5[i].push_back(host[i]);
v_5[host[i]].push_back(i);
}
if(protocol[i]==1){
for(int j:v_5[host[i]]){
v_5[j].push_back(i);
v_5[i].push_back(j);
}
}
if(protocol[i]==2){
for(int j:v_5[host[i]]){
v_5[j].push_back(i);
v_5[i].push_back(j);
}
v_5[i].push_back(host[i]);
v_5[host[i]].push_back(i);
}
}
for(int i=0;i<n;i++){
if(!vis_5[i]){
dfs_5(i,i);
}
}
for(int i=0;i<n;i++){
if(bw_5[i]){
e_5[n].push_back({i,1,e_5[i].size()});
e_5[i].push_back({n,0,e_5[n].size()-1});
for(int j:v_5[i]){
e_5[i].push_back({j,0xE869120,e_5[j].size()});
e_5[j].push_back({i,0,e_5[i].size()-1});
}
}
else{
e_5[i].push_back({n+1,1,e_5[n+1].size()});
e_5[n+1].push_back({i,0,e_5[i].size()-1});
}
}
return n-calc_max_flow_5(n);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
if(n<=10){
return solve_1(n,confidence,host,protocol);
}
bool used[3],f;
for(int i=0;i<3;i++)used[i]=false;
f=true;
for(int i=1;i<n;i++){
if(confidence[i]!=1)f=false;
used[protocol[i]]=true;
}
if(!used[0]&&used[1]&&!used[2]){
return solve_2(n,confidence,host,protocol);
}
if(!used[0]&&!used[1]&&used[2]){
return solve_3(n,confidence,host,protocol);
}
if(used[0]&&!used[1]&&!used[2]){
return solve_4(n,confidence,host,protocol);
}
if(f&&!used[2]){
return solve_5(n,confidence,host,protocol);
}
return -1;
}
