#include<bits/stdc++.h>
#include "friend.h"
#define MAXN 1007
using namespace std;
struct edge{
int to;
bool cap;
int rev;
};
int n;
vector<int> v[MAXN];
vector<edge> g[MAXN];
long long ans,cost[MAXN];
int mins,maxs,where[MAXN];
bool li[MAXN];
void brute(int x,long long res){
if(x==0){
ans=max(ans,res);
return;
}
brute(x-1,res);
int br=0;
for(int i:v[x]){
if(li[i])br++;
}
if(br==0){
li[x]=true;
brute(x-1,res+cost[x]);
li[x]=false;
}
}
long long dp[MAXN][2];
bool vis[MAXN][2];
long long ff(int x,int p,int parent){
if(vis[x][p])return dp[x][p];
vis[x][p]=true;
if(p==0){
dp[x][p]=cost[x];
for(int i:v[x]){
if(i==parent)continue;
dp[x][p]+=ff(i,1,x);
}
}
long long sum=0;
for(int i:v[x]){
if(i==parent)continue;
sum+=ff(i,0,x);
}
dp[x][p]=max(dp[x][p],sum);
return dp[x][p];
}
void add_edge(int from,int to){
g[from].push_back({to,1,int(g[to].size())});
g[to].push_back({from,0,int(g[from].size())-1});
}
int source,sink,flow,maxflow,mvc;
void dfs(int x,int side){
li[x]=true;
where[x]=side;
if(side==0)add_edge(source,x);
if(side==1)add_edge(x,sink);
for(int i:v[x]){
if(side==0)add_edge(x,i);
if(li[i])continue;
dfs(i,side^1);
}
}
int u[MAXN],tim;
int fordfulk(int x){
if(x==sink)return 1;
u[x]=tim;
for(int i=0;i<g[x].size();i++){
if(u[g[x][i].to]==tim or !g[x][i].cap)continue;
int curr=fordfulk(g[x][i].to);
if(curr>0){
g[x][i].cap=false;
g[g[x][i].to][g[x][i].rev].cap=true;
return 1;
}
}
return 0;
}
void dfs2(int x){
u[x]=tim;
for(int i=0;i<g[x].size();i++){
if(u[g[x][i].to]==tim or !g[x][i].cap)continue;
dfs2(g[x][i].to);
}
}
int findSample(int N,int confidence[],int host[],int protocol[]){
//int findSample(int N,vector<int> confidence,vector<int> host,vector<int> protocol){
n=N;
for(int i=0;i<n;i++)cost[i+1]=confidence[i];
mins=3; maxs=0;
for(int i=1;i<=n-1;i++){
mins=min(mins,protocol[i]);
maxs=max(maxs,protocol[i]);
}
if(mins==maxs and mins==1){
for(int i=1;i<=n;i++)ans+=cost[i];
return ans;
}else if(mins==maxs and mins==2){
for(int i=1;i<=n;i++)ans=max(ans,cost[i]);
return ans;
}
for(int i=1;i<=n-1;i++){
if(protocol[i]==0 or protocol[i]==2){
v[host[i]+1].push_back(i+1);
v[i+1].push_back(host[i]+1);
}
if(protocol[i]==1 or protocol[i]==2){
for(int f:v[host[i]+1]){
v[f].push_back(i+1);
v[i+1].push_back(f);
}
}
}
if(n<=20){
brute(n,0);
return ans;
}else if(mins==maxs and mins==0){
return ff(0,0,-1);
}
source=0; sink=n+1;
for(int i=1;i<=n;i++){
if(!li[i])dfs(i,0);
}
while(true){
tim++;
flow=fordfulk(source);
if(flow==0)break;
maxflow+=flow;
}
tim++; u[source]=u[sink]=tim;
for(int i=0;i<g[source].size();i++){
if(g[source][i].cap and u[g[source][i].to]!=tim){
dfs2(g[source][i].to);
}
}
for(int i=1;i<=n;i++){
if(where[i]==0 and u[i]!=tim)mvc++;
if(where[i]==1 and u[i]==tim)mvc++;
}
return n-mvc;
}
/*int main(){
cout<<findSample(9,{1,1,1,1,1,1,1,1,1},{0,0,1,1,3,3,3,6,6},{0,0,0,0,0,0,0,0,0})<<"\n";
return 0;
}*/
