//#include "grader.cpp"
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(n) push_back(n)
const int N=1e5+5;
int dp[N][2], conf[N], used[N], match[N];
vector<vector<int>>v;
vector<int>l, r, edges[1005];
void add(int a,int b){
v[a].pb(b);
v[b].pb(a);
}
//if all 0
void dfs(int ei,int prev){
dp[ei][1]=conf[ei];
for(auto x : edges[ei]){
if(x == prev) continue;
dfs(x,ei);
dp[ei][0] += dp[x][1];
dp[ei][1] += dp[x][0];
}
dp[ei][1]=max(dp[ei][0],dp[ei][1]);
}
//divide into two part left and right and solve with bipartite
void bpart(int ei, int col=0){
if(col == 0) l.pb(ei);
else r.pb(ei);
used[ei] = true;
for(auto x : edges[ei]){
if(used[x])continue;
bpart(x, col^1);
}
}
//check if matches
bool check(int ei, int time){
used[ei]=time;
for(auto x : edges[ei]){
if(match[x]==-1 || used[match[x]]!=time && check(match[x], time)) {
match[x]=ei;
return 1;
}
}return 0;
}
//main function
int findSample(int n,int c[],int h[],int p[]){
int ans=0;
for(int i=0;i<n;i++){
conf[i]=c[i];
}
bool e0=1, e1=1, e2=1;
for(int i=1;i<n;i++){
e0=(p[i]!=0?0:e0);
e1=(p[i]!=1?0:e1);
e2=(p[i]!=2?0:e2);
}
// if n <= 15
if(n<=15){
v.resize(n);
for(int i=1;i<n;i++){
if(p[i]==0) add(h[i],i);
else{
for(auto x:v[h[i]]) add(x,i);
if(p[i]==2) add(h[i],i);
}
}
int mask=1;
while(mask < (1<<n)){
int cost=0;
vector<int> used1(n,0);
for(int i=0;i<n;i++){
if(!((1<<i)&mask)) continue;
bool ok=1;
for(auto x:v[i]) if(used1[x]) ok=0;
if(ok){
cost+=c[i];
used1[i]=1;
}
}
ans=max(ans,cost);
mask++;
}
return ans;
}
// if all 1
else if(e1){
for(int i=0;i<n;i++) ans += c[i];
}
// if all 2
else if(e2){
for(int i=0;i<n;i++) ans = max(ans, c[i]);
}
// if all 0
else if(e0){
for(int i=1;i<n;i++){
edges[i].pb(h[i]);
edges[h[i]].pb(i);
}
dfs(0, 0);
ans = dp[0][1];
}
// if 1 and 0
else {
for(int i=1;i<n;i++){
if(p[i] == 0){
edges[i].pb(h[i]);
edges[h[i]].pb(i);
}else {
for(auto x : edges[h[i]]){
edges[i].pb(x);
edges[x].pb(i);
}
if(p[i] == 2){
edges[i].pb(h[i]);
edges[h[i]].pb(i);
}
}
}
for(int i=0;i<n;i++) if(!used[i])bpart(i);
int s = 1001, e = 1002;
for(auto x : l) edges[s].pb(x);
for(auto x : r) edges[x].pb(e);
for(int i=0;i<n;i++) match[i] = -1;
int timer = 0;
for(auto ei : l){
timer++;
ans += check(ei, timer);
}ans = n-ans;
}
return ans;
}
/*
6
13 3 6 20 10 15
0 0 1 1 2 0
0 0 1 1 1 0
*/
