#include "bits/stdc++.h"
#include "friend.h"
using namespace std;
const int MAXN = 100100;
int n, val[MAXN], person[MAXN], type[MAXN];
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define all(x) (x).begin(), (x).end()
int Subtask1(){
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
if (type[i] == 0) {
g[i].push_back(person[i]);
g[person[i]].push_back(i);
}
if (type[i] == 1) {
for (int j : g[person[i]]) {
if (j == person[i]) continue;
g[i].push_back(j);
g[j].push_back(i);
}
}
if (type[i] == 2) {
g[i].push_back(person[i]);
g[person[i]].push_back(i);
for (int j : g[person[i]]) {
if (j == person[i]) continue;
g[i].push_back(j);
g[j].push_back(i);
}
}
}
vector<vector<int>> gg(n, vector<int>(n, 0));
// cout << "\nedges\n";
for (int i = 0; i < n; i++) {
for (int j : g[i]) gg[i][j] = 1;
// for (int j : g[i]) cout << i << ' ' << j << endl;
}
// cout << "\nedges\n";
int ans = 0;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> vec;
int cur = 0;
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue;
vec.push_back(i);
cur += val[i];
}
bool ok = true;
for (int i : vec) {
for (int j : vec) {
if (i != j && gg[i][j]) ok = false;
}
}
if (ok) ans = max(ans, cur);
}
return ans;
}
int Subtask2(){
return accumulate(val, val + n, 0);
}
int Subtask3(){
vector<int> p(n);
iota(all(p), 0);
function<int(int)> find = [&](int x) {
return x == p[x] ? x : p[x] = find(p[x]);
};
function<void(int, int)> unite = [&](int x, int y){
x = find(x);
y = find(y);
if (x == y) return;
if (rng() & 1) swap(x, y);
p[x] = y;
};
for (int i = 1; i < n; i++){
unite(person[i], i);
}
map<int, int> mp;
for (int i = 0; i < n; i++){
int x = find(i);
mp[x] = max(mp[x], val[i]);
}
int ans = 0;
for (auto now : mp) ans += now.second;
return ans;
}
int findSample(int _n, int _val[], int _person[], int _type[]){
n = _n;
for (int i = 0; i < n; i++) val[i] = _val[i], person[i] = _person[i], type[i] = _type[i];
bool IAm = count(type + 1, type + n, 0) > 0;
bool MyFriends = count(type + 1, type + n, 1) > 0;
bool WeAre = count(type + 1, type + n, 2) > 0;
if (n <= 10) Subtask1();
if (!IAm && MyFriends && !WeAre) return Subtask2();
if (!IAm && !MyFriends && WeAre) return Subtask3();
return -1;
}
