#include <bits/stdc++.h>
#include "friend.h"
#define allof(x) x.begin(),x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
struct Query{
int u,v,type;
Query(): u(0),v(0),type(0) {}
Query(int U,int V,int T): u(U), v(V), type(T) {}
};
int findSample(int n, int confidence[], int host[], int protocol[]){
vector<Query> queries;
for (int i=1;i<n;i++) queries.emplace_back(host[i],i,protocol[i]);
reverse(allof(queries));
int dp[n+1][2];
mset(dp,0);
for (int i=0;i<n;i++) dp[i][1] = confidence[i];
for (Query qr : queries){
int type = qr.type;
int u = qr.u;
int v = qr.v;
if (!type){
dp[u][1] += dp[v][0];
dp[u][0] += max(dp[v][1],dp[v][0]);
} else if (type==1){
dp[u][1] = max({dp[u][1] + dp[v][0],dp[u][0] + dp[v][1],dp[u][1] + dp[v][1]});
dp[u][0] += dp[v][0];
} else{
dp[u][1] = max(dp[u][1] + dp[v][0],dp[u][0] + dp[v][1]);
dp[u][0] += dp[v][0];
}
}
return max(dp[0][0],dp[0][1]);
}
