#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)
pll solve(ll i, const vll& c, const vvpll& adj, vpll& dp) {
pll& ans = dp[i];
if(ans.fi == -1ll) {
ans.fi = c[i];
ans.se = 0ll;
for(ll ind = adj[i].size() - 1ll; ind >= 0; ind--) {
ll j = adj[i][ind].fi;
ll pr = adj[i][ind].se;
pll recurs = solve(j, c, adj, dp);
ll ins_pick = recurs.fi, ins_nopick = recurs.se;
ll new_pick, new_nopick;
if(pr == 0ll) {
new_pick = ans.fi + ins_nopick;
new_nopick = ans.se + max(ins_pick, ins_nopick);
} else if (pr == 1ll) {
new_pick = max(ans.fi + max(ins_pick, ins_nopick), ins_pick + ans.se);
new_nopick = ans.se + ins_nopick;
} else if(pr == 2ll) {
new_pick = max(ans.fi + ins_nopick, ans.se + ins_pick);
new_nopick = ans.se + ins_nopick;
}
ans.fi = new_pick;
ans.se = new_nopick;
}
}
return ans;
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
vvpll adj;
vll c;
for(ll i = 0; i < n; i++) {
vpll adjr;
adj.pb(adjr);
c.pb(confidence[i]);
}
for(ll i = 1; i < n; i++) {
adj[(ll)host[i]].pb({i, (ll)protocol[i]});
}
vpll dp(n, {-1ll, -1ll});
pll ans = solve(0ll, c, adj, dp);
return max(ans.fi, ans.se);
}
