#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "friend.h"
const int MAX = 1005;
int N;
vi c(MAX);
vi cr(MAX); // c, taken maximum over equiv
vi hs(MAX);
vi type(MAX);
vi base(MAX); // top vertex mapped to
vi adj[MAX];
vector<bool> vis(MAX, false);
vector<ll> s1(MAX, 0); // max sum if use vertex
vector<ll> s2(MAX, 0); // max sum if not use vertex
void dfs(int n) {
vis[n] = true;
s1[n] = cr[n];
for (int x : adj[n]) {
if (!vis[x] && cr[x] != 0) {
dfs(x);
s2[n] += max(s1[x], s2[x]);
s1[n] += s2[x];
}
}
}
void reset() {
for (int i = 0; i < N; i++) {
c[i] = 0;
cr[i] = 0;
hs[i] = 0;
type[i] = 0;
base[i] = 0;
adj[i].clear();
vis[i] = false;
s1[i] = 0;
s2[i] = 0;
}
}
int findSample(int n, int confidence[], int hst[], int protocol[]) {
N = n;
reset();
for (int i = 0; i < N; i++) {
c[i] = confidence[i];
cr[i] = confidence[i];
hs[i] = hst[i];
type[i] = protocol[i];
base[i] = i;
}
for (int i = 1; i < N; i++) {
hs[i] = base[hs[i]];
if (type[i] == 0) {
adj[i].pb(hs[i]);
adj[hs[i]].pb(i);
}
else if (type[i] == 1) {
for (int x : adj[hs[i]]) {
adj[i].pb(x);
adj[x].pb(i);
}
}
else {
base[i] = base[hs[i]];
cr[base[i]] = max(cr[base[i]], c[i]);
cr[i] = 0;
}
}
/* cout<<"adj: "<<endl;
for (int i = 0; i < N; i++) {
cout<<i<<": ";
for (int x : adj[i])
cout<<x<<" ";
cout<<endl;
}
cout<<"cr: ";
for (int i = 0; i < N; i++) {
cout<<cr[i]<<" ";
}
cout<<endl;*/
// have bipartite graph w/o cycles, do bfs
vi heads;
for (int i = 0; i < N; i++) {
if (!vis[i] && (cr[i] != 0)) {
heads.pb(i);
dfs(i);
}
}
/* cout<<"s1: ";
for (int i = 0; i < N; i++) {
cout<<s1[i]<<" ";
}
cout<<endl;
cout<<"s2: ";
for (int i = 0; i < N; i++) {
cout<<s2[i]<<" ";
}
cout<<endl;
cout<<"heads: ";
for (int x : heads)
cout<<x<<" ";
cout<<endl;*/
ll total = 0;
for (int x : heads) {
total += max(s1[x], s2[x]);
}
return (int)(total);
}
