#include "friend.h"
#include <algorithm>
#include <vector>
// Find out best sample
std::vector<std::vector<int>>v;
std::vector<int>a;
int ans=0;
void dfs(int x,int p,int c1,int c2,int cur){
if(cur) c1+=a[x];
else c2+=a[x];
ans=std::max(ans,c2);
ans=std::max(ans,c1);
for(int z:v[x]){
if(z!=p){
dfs(z,x,c1,c2,cur^1);
}
}
}
int sub4(int n,int confidence[],int host[]){
v.resize(n);
a.resize(n);
for(int i=0;i<n;i++) a[i]=confidence[i];
for(int i=1;i<n;i++){
v[i].push_back(host[i]);
v[host[i]].push_back(i);
}
dfs(0,0,0,0,0);
return ans;
}
int findSample(int n,int confidence[],int host[],int protocol[]){
if(protocol[1]==0) return sub4(n,confidence,host);
for(int i=0;i<n;i++) ans=(protocol[1]&1 ? ans+confidence[i] : std::max(ans,confidence[i]));
return ans;
}
