#include "bits/stdc++.h"
#include "friend.h"
using namespace std;
const int MAXN = 100100;
int n, val[MAXN], root[MAXN], type[MAXN];
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define all(x) (x).begin(), (x).end()
vector<vector<int>> get_graph(){
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
if (type[i] == 0) {
g[i].push_back(root[i]);
g[root[i]].push_back(i);
}
if (type[i] == 1) {
for (int j : g[root[i]]) {
if (j == root[i]) continue;
g[i].push_back(j);
g[j].push_back(i);
}
}
if (type[i] == 2) {
g[i].push_back(root[i]);
g[root[i]].push_back(i);
for (int j : g[root[i]]) {
if (j == root[i]) continue;
g[i].push_back(j);
g[j].push_back(i);
}
}
}
return g;
}
int Subtask1(){
vector<vector<int>> g = get_graph();
vector<vector<int>> gg(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j : g[i]) gg[i][j] = 1;
}
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(root[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 Subtask4(){
vector<vector<int>> g(n);
for (int i = 1; i < n; i++){
g[i].push_back(root[i]);
g[root[i]].push_back(i);
}
function<pair<int, int>(int, int)> dfs = [&](int v, int p){
pair<int, int> res = make_pair(val[v], 0);
for (int u : g[v]){
if (u == p) continue;
pair<int, int> dp = dfs(u, v);
res.first += dp.second;
res.second += max(dp.first, dp.second);
}
return res;
};
pair<int, int> ans = dfs(1, 1);
return max(ans.first, ans.second);
}
int Subtask5(){
vector<vector<int>> g = get_graph();
vector<int> color(n, -1);
vector<int> comp;
function<bool(int, int)> dfs = [&](int v, int x){
color[v] = x;
comp.push_back(v);
for (int u : g[v]){
if (color[u] == -1 && dfs(u, x ^ 1)) return true;
if (color[u] == x) return false;
}
return false;
};
int ans = 0;
for (int i = 0; i < n; i++){
if (color[i] == -1){
comp.clear();
dfs(i, 0);
int black = 0, white = 0;
for (int x : comp){
// cout << x << ' ';
if (color[x] == 0){
white += val[x];
} else {
black += val[x];
}
}
// cout << endl << endl;
ans += max(black, white);
}
}
return ans;
}
int findSample(int _n, int _val[], int _host[], int _type[]){
n = _n;
for (int i = 0; i < n; i++) val[i] = _val[i], root[i] = _host[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;
return Subtask5();
if (n <= 10) return Subtask1();
if (!IAm && MyFriends && !WeAre) return Subtask2();
if (!IAm && !MyFriends && WeAre) return Subtask3();
if (IAm && !MyFriends && !WeAre) return Subtask4();
return -1;
}
