#include<bits/stdc++.h>
// Define
const int N = 100005;
using namespace std;
int da[N], nu[N];
struct sonsh{
int nod, pt;
};
vector<sonsh> sons[N];
int cost[N];
// Find out answer
void dfs(int nod){
da[nod] = cost[nod];
nu[nod] = 0;
for(int i = sons[nod].size() - 1; i>=0; i--){
int sn = sons[nod][i].nod;
dfs(sn);
int dah = 0, nuh = 0;
if(sons[nod][i].pt == 0){ // IAmYourFriend
dah = da[nod] + nu[sn];
nuh = max(nu[nod] + nu[sn], nu[nod] + da[sn]);
}
else if(sons[nod][i].pt == 1){ // MyFriendsAreYourFriends
dah = max({nu[nod] + da[sn], da[nod] + nu[sn], da[nod] + da[sn]});
nuh = nu[nod] + nu[sn];
}
else if(sons[nod][i].pt == 2){ // We AreYourFriends
dah = max({nu[nod] + da[sn], da[nod] + nu[sn]});
nuh = nu[nod] + nu[sn];
}
da[nod] = dah;
nu[nod] = nuh;
}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
for(int i = 0; i < n; i++)
cost[i] = confidence[i];
for(int i = 1; i < n; i++){
sons[host[i]].push_back({i, protocol[i]});
}
dfs(0);
return max(da[0], nu[0]);
}
