#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
namespace BPM{
vector<int>adj[1010];
int match[1010],dep[1010],match1[1010],match2[1010],col[1010];
bitset<1010>vis;
void AE(int x,int y){
x++,y++;
adj[x].push_back(y);
adj[y].push_back(x);
}
int bfs(int n){
queue<int>q;
for(int i=1;i<=n;i++) if(col[i]){
if(!match1[i])
q.push(i),
dep[i]=1;
else dep[i]=0;}
dep[0]=0;
while(q.size()){
int x=q.front();
q.pop();
if(dep[x]>=dep[0]&&dep[0])
continue;
for(auto i:adj[x])
if(!dep[match2[i]])
dep[match2[i]]=dep[x]+1,
q.push(match2[i]);
}
return dep[0];
}
int dfs(int n){
if(!n)return 1;
for(auto i:adj[n]){
if(dep[match2[i]]==dep[n]+1&&dfs(match2[i]))
return match2[match1[n]=i]=n,1;
}
dep[n]=1e9;
return 0;
}
void dfsc(int i){
vis[i]=1;
for(auto n:adj[i]) if(!vis[n])
col[n]=!col[i],dfsc(n);
}
int runmatch(int n){
for(int i=1;i<=n;i++)
if(!vis[i])
dfsc(i);
int ans=0;
while(bfs(n))for(int i=1;i<=n;i++)
if(!match1[i]&&col[i]) ans+=dfs(i);
return ans;
}
}
vector<int>adj[1010];
void AE(int x,int y){
adj[x].push_back(y);
adj[y].push_back(x);
}
int bruteforce(int n,int confidence[],int host[],int protocol[]){
for(int i=1;i<n;i++){
if(protocol[i])
for(auto x:adj[host[i]])
AE(x,i);
if(protocol[i]%2==0)
AE(i,host[i]);
}
int ans=0;
for(int msk=1;msk<1<<n;msk++){
int conf=0;
for(int i=0;i<n;i++) if(msk&1<<i)
conf+=confidence[i];
for(int i=0;i<n;i++) if(msk&1<<i)
for(auto y:adj[i]) if(msk&1<<y)
conf=-1; ans=max(ans,conf);
}
return ans;
}
int wieht[1010],dp1[1010],dp2[1010];
void dfs(int n){
dp1[n]=0;
dp2[n]=wieht[n];
for(auto x:adj[n]){
dfs(x);
dp2[n]+=dp1[x];
dp1[n]+=max(dp2[x],dp1[x]);
}
}
int itsatree(int par[],int conf[],int n){
for(int i=1;i<n;i++)
adj[par[i]].push_back(i);
memcpy(wieht,conf,4*n);
dfs(0);
return max(dp1[0],dp2[0]);
}
int amatching(int host[],int protoc[],int n){
for(int i=1;i<n;i++){
if(protoc[i])
for(auto x:BPM::adj[host[i]+1])
BPM::AE(x,i);
else BPM::AE(i,host[i]);
}
return n-BPM::runmatch(n);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
//if(n<=10) return bruteforce(n,confidence,host,protocol);
set<int>st;
int ans=0,ans2=0;
for(int i=0;i<n;i++)
ans+=confidence[i],ans2=max(ans2,confidence[i]);
for(int i=1;i<n;i++)
st.insert(protocol[i]);
if(st.size()==1)
return protocol[1]==1?ans:protocol[1]?ans2:itsatree(host,confidence,n);
return amatching(host,protocol,n);
}
