#include "friend.h"
#include <vector>
#include <array>
#include <algorithm>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[])
{
std::vector<std::array<int, 2> > dp(n);
//0) I am not used
//1) I am used
for(int i=0;i<n;++i)
dp[i]={0, confidence[i]};
for(int i=n-1;i>0;--i)
{
int h = host[i];
if(protocol[i] == 0)
{
dp[h][0] += std::max(dp[i][0], dp[i][1]);
dp[h][1] += dp[i][0];
}
else if(protocol[i] == 1)
{
dp[h][1] += std::max(dp[i][0], dp[i][1]);
ckmax(dp[h][1], dp[h][0]+dp[i][1]);
dp[h][0] += dp[i][0];
}
else if(protocol[i] == 2)
{
dp[h][1] += dp[i][0];
ckmax(dp[h][1], dp[h][0]+dp[i][1]);
dp[h][0] += dp[i][0];
}
}
return std::max(dp[0][0], dp[0][1]);
}
