#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) int(x.size())
const int MXN = 1e5+5;
int dp[MXN][2], suf[MXN], pre[MXN];
vector<int> g[MXN];
int findSample(int n,int confidence[],int host[],int protocol[]) {
for(int i=1; i<n; i++) g[host[i]].push_back(i);
for(int v=n-1; v>=0; v--) {
if(g[v].empty()) {
dp[v][1] = confidence[v];
continue;
}
for(int i=0; i<SZ(g[v]); i++) {
pre[i] = i ? pre[i-1] : 0;
pre[i] += (protocol[g[v][i]]==1) ? max(dp[g[v][i]][0], dp[g[v][i]][1]) : dp[g[v][i]][0];
}
for(int i=SZ(g[v])-1; i>=0; i--) {
suf[i] = i+1<SZ(g[v]) ? suf[i+1] : 0;
suf[i] += protocol[g[v][i]] ? dp[g[v][i]][0] : max(dp[g[v][i]][0], dp[g[v][i]][1]);
}
dp[v][0] = suf[0];
dp[v][1] = pre[SZ(g[v])-1] + confidence[v];
for(int i=0; i<SZ(g[v]); i++)
if(protocol[g[v][i]])
dp[v][1] = max(dp[v][1], dp[g[v][i]][1] + (i ? pre[i-1] : 0) + (i+1<SZ(g[v]) ? suf[i+1] : 0));
}
return max(dp[0][0], dp[0][1]);
}
