#include "friend.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#define ll long long
using namespace std;
vector <ll> adj[100000];
ll dp[100000][4], cur[8][2], p, c, f = 0;
int findSample(int n,int confidence[],int host[],int protocol[]) {
for (int i=0; i<n; ++i) {
dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = 0;
}
for (int i=n-1; i>0; --i) {
p = host[i], c = confidence[i];
if (protocol[i] == 0) {
dp[p][2] += max(dp[i][0], dp[i][1]);
dp[p][3] = max(dp[p][3] + max(dp[i][0], dp[i][1]), max(dp[p][0], dp[p][1]) + max(max(dp[i][0], dp[i][2]) + c, max(dp[i][1], dp[i][3])));
dp[p][0] += max(dp[i][0], dp[i][1]);
dp[p][1] += max(max(dp[i][0] + c, dp[i][1]), max(dp[i][2]+c, dp[i][3]));
}
else if (protocol[i] == 1) {
dp[p][2] += max(max(dp[i][0] + c, dp[i][1]), dp[i][2] + c);
dp[p][3] += max(max(dp[i][0] + c, dp[i][1]), max(dp[i][2] + c, dp[i][3]));
dp[p][0] += max(dp[i][0], dp[i][1]);
dp[p][1] += max(dp[i][0], dp[i][1]);
}
else {
dp[p][2] += max(dp[i][0], dp[i][1]);
dp[p][3] = max(dp[p][3] + max(dp[i][0], dp[i][1]), max(dp[p][0], dp[p][1]) + max(max(dp[i][0], dp[i][2]) + c, max(dp[i][1], dp[i][3])));
dp[p][0] += max(dp[i][0], dp[i][1]);
dp[p][1] += max(dp[i][0], dp[i][1]);
}
}
dp[0][0] += confidence[0], dp[0][2] += confidence[0];
for (int i=0; i<4; ++i) {
f = max(f, dp[0][i]);
}
return f;
}
