#include "friend.h"
#include <algorithm>
#include <vector>
// Find out best sample
std::vector<std::vector<int>>v,dp;
std::vector<int>a;
int ans=0;
void dfs(int x,int p){
dp[x][1]=a[x];
for(int z:v[x]){
if(z!=p){
dfs(z,x);
dp[x][0]+=std::max(dp[z][1],dp[z][0]);
dp[x][1]+=dp[z][0];
}
}
}
int sub4(int n,int confidence[],int host[]){
v.resize(n);
a.resize(n);
dp.assign(n,std::vector<int>(2,0));
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);
return std::max(dp[0][0],dp[0][1]);
}
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;
}
