#include "friend.h"
// Find out best sample
int sum[100001][2];
int max(int a,int b){ return a>b?a:b; }
int min(int a,int b){ return a<b?a:b; }
bool edge[11][11];
int naive(int n,int cf[],int hst[],int pt[]){
for(int i=1; i<n; ++i){
int h=hst[i];
if(pt[i] == 0){
edge[h][i]=edge[i][h]=true;
} else {
for(int j=0; j<n; ++j) if(edge[h][j]) edge[j][i]=edge[i][j]=true;
if(pt[i] == 2){
edge[h][i]=edge[i][h]=true;
}
}
}
int msk=(1<<n);
int ans=0;
for(int i=0; i<msk; ++i){
int s[11], t=0;
int cur=0;
for(int j=0; j<n; ++j) if(1&(i>>j)) s[t++]=j, cur+=cf[j];
bool wa=0;
for(int a=0; a<t; ++a){
for(int b=a+1; b<t; ++b){
if(edge[s[a]][s[b]]){
wa=1; break;
}
}
if(wa) break;
}
if(!wa) ans=max(ans, cur);
}
return ans;
}
#include <cstdio>
int findSample(int n,int confidence[],int host[],int protocol[]){
if(n <= 10){
// return naive(n,confidence,host, protocol);
}
for(int i=0; i<n; ++i) sum[i][1]=confidence[i], sum[i][0]=0;
int allprot=0;
for(int i=n-1; 0<i; --i){
int h=host[i];
int p=protocol[i];
if(p==2) ++allprot;
if(p == 0){
sum[h][0] += max(sum[i][0], sum[i][1]);
sum[h][1] += sum[i][0];
} else if(p == 1){
sum[h][0] += sum[i][0];
sum[h][1] += max(sum[i][0], sum[i][1]);
} else if(p == 2){
sum[h][1] += max(0, -confidence[h] + max(sum[i][0], sum[i][1]));
sum[h][0] += sum[i][0];
}
//printf("Host(%d)| %d %d\n", h, sum[h][1], sum[h][0]);
}
if(allprot == n-1){
int ans=0;
for(int i=0; i<n; ++i) ans=max(ans, confidence[i]);
return ans;
}
return max(sum[0][0], sum[0][1]);
}
