#include<bits/stdc++.h>
#include "friend.h"
using namespace std;
int subtask1(int n, int c[], int h[], int p[]){
vector<set<int> > adi(n);
for(int i=1; i<n; i++){
if(p[i]==0){
adi[h[i]].insert(i);
adi[i].insert(h[i]);
}
else if(p[i]==1){
for(auto u: adi[h[i]]){
adi[u].insert(i);
adi[i].insert(u);
}
}
else{
for(auto u: adi[h[i]]){
adi[u].insert(i);
adi[i].insert(u);
}
adi[h[i]].insert(i);
adi[i].insert(h[i]);
}
}
int ans=0;
for(int i=0; i<(1<<n); i++){
vector<int> active;
int mom=0;
for(int j=0; j<n; j++){
if((i>>j)%2==1){
mom+=c[j];
active.push_back(j);
}
}
for(auto v: active){
for(auto u: active){
if(adi[v].find(u)!=adi[v].end()) mom=0;
}
}
ans=max(ans, mom);
}
return ans;
}
bool issubtask2(int n, int protocol[]){
for(int i=1; i<n; i++){
if(protocol[i]!=1) return false;
}
return true;
}
int subtask2(int n, int confidence[]){
int ans=0;
for(int i=0; i<n; i++){
ans+=confidence[i];
}
return ans;
}
bool issubtask3(int n, int protocol[]){
for(int i=1; i<n; i++){
if(protocol[i]!=2) return false;
}
return true;
}
int subtask3(int n, int confidence[]){
int ans=0;
for(int i=0; i<n; i++){
ans=max(ans, confidence[i]);
}
return ans;
}
bool issubtask4(int n, int protocol[]){
for(int i=1; i<n; i++){
if(protocol[i]!=0) return false;
}
return true;
}
void dfs(int v, vector<vector<int> >& adi, vector<vector<int> >& dp, int c[]){
dp[v][0]=0;
dp[v][1]=c[v];
for(auto u: adi[v]){
dfs(u, adi, dp, c);
dp[v][0]+=max(dp[u][0], dp[u][1]);
dp[v][1]+=dp[u][0];
}
}
int subtask4(int n, int c[], int h[], int p[]){
vector<vector<int> > adi(n);
for(int i=1; i<n; i++){
adi[h[i]].push_back(i);
}
vector<vector<int> > dp(n, vector<int> (2, -1));
dfs(0, adi, dp, c);
return max(dp[0][0], dp[0][1]);
}
int findSample(int n,int confidence[],int host[],int protocol[]){
if(n<=10){
return subtask1(n, confidence, host, protocol);
}
if(issubtask2(n, protocol)){
return subtask2(n, confidence);
}
if(issubtask3(n, protocol)){
return subtask3(n, confidence);
}
if(issubtask4(n, protocol)){
return subtask4(n, confidence, host, protocol);
}
return -1;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}*/
