#include "friend.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 1e5 + 5;
int p[MAX_N], q[MAX_N];
int findSample(int n, int confidence[], int host[], int protocol[]) {
for (int i = 0; i < n; i++) p[i] = confidence[i];
for (int i = n - 1; i; i--) {
int j = host[i];
if (!protocol[i]) {
p[j] += q[i];
q[j] += max(p[i], q[i]);
} else if (protocol[i] == 1) {
p[j] = max({p[i] + p[j], p[i] + q[j], q[i] + p[j]});
q[j] += q[i];
} else {
p[j] = max(p[i] + q[j], q[i] + p[j]);
q[j] += q[i];
}
}
return max(p[0], q[0]);
}
