#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]);
}
int solve_5(int n,int confidence[],int host[],int protocol[]){
return -1;
}
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;
}
