#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int findSample(int n,int confidence[],int host[],int protocol[]){
vector<vector<int>> t(n);
vector<int[2]> dp(n);
for (int i = 1; i < n; ++i) {
t[host[i]].push_back(i);
}
for (int i = n; i--;) {
for (int f = 0; f < 2; ++f) {
int sm = 0;
for (int v: t[i]) {
if (protocol[v] == 0) sm += dp[v][1];
else sm += dp[v][0];
}
dp[i][f] = max(dp[i][f], sm);
for (int v: t[i]) {
if (protocol[v] == 0) sm += dp[v][0] - dp[v][1];
else if (f) sm += dp[v][1] - dp[v][0];
dp[i][f] = max(dp[i][f], sm);
if (f && protocol[v] == 2) sm += dp[v][0] - dp[v][1];
}
if (f) sm += confidence[i];
dp[i][f] = max(dp[i][f], sm);
}
}
return dp[0][1];
}
