#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
const int INF = 1e9;
int a[N];
int h[N];
int f[N][16];
bool e[N][4];
bool visit[N];
vector<int> G[N];
void add(int u, int v) {
G[u].push_back(v), G[v].push_back(u);
}
void dfs(int u) {
visit[u] = 1;
for (auto v : G[u]) {
if (!visit[v]) {
h[v] = h[u] + 1, dfs(v);
}
else if (h[u] > h[v]) {
e[u][h[u] - h[v]] = 1;
}
}
}
void solve(int u) {
visit[u] = 1;
for (int i = 0; i < 16; ++i) {
if (i & 1) f[u][i] = a[u];
for (int j = 1; j < 4; ++j) {
if ((i & 1) && (i >> j & 1) && e[u][j]) {
f[u][i] = -INF; break;
}
}
}
for (auto v : G[u]) {
if (visit[v]) continue;
solve(v);
for (int j = 0; j < 16; ++j) {
int mask = (j << 1) & 15;
int tmp = max(f[v][mask], f[v][mask + 1]);
f[u][j] = max(-INF, f[u][j] + tmp);
}
}
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
if (n > 1000) return 0;
for (int i = 0; i < n; ++i) {
a[i] = confidence[i];
}
for (int i = 1; i < n; ++i) {
if (protocol[i] == 0) {
add(host[i], i);
}
if (protocol[i] == 1) {
for (auto j : G[host[i]]) add(i, j);
}
if (protocol[i] == 2) {
for (auto j : G[host[i]]) add(i, j);
add(host[i], i);
}
}
dfs(0);
memset(visit, 0, sizeof visit);
solve(0);
int res = -INF;
for (int i = 0; i < 16; ++i) res = max(res, f[0][i]);
return res;
}
