#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
int findSample(int n, int val[], int host[], int prot[]) {
vi sel(n),nsel(n,0);
for (int i=0; i<n; i++) {
sel[i]=val[i];
}
for (int i=n-1; i>0; i--) {
if (prot[i]==0) {
int newsel=sel[host[i]]+nsel[i];
nsel[host[i]]=nsel[host[i]]+max(sel[i],nsel[i]);
sel[host[i]]=newsel;
}
else if (prot[i]==1) {
int newsel=max(sel[i]+sel[host[i]],max(nsel[i]+sel[host[i]],sel[i]+nsel[host[i]]));
nsel[host[i]]=nsel[host[i]]+nsel[i];
sel[host[i]]=newsel;
}
else {
int newsel=max(nsel[i]+sel[host[i]],sel[i]+nsel[host[i]]);
nsel[host[i]]=nsel[host[i]]+nsel[i];
sel[host[i]]=newsel;
}
}
return max(sel[0],nsel[0]);
}
