#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define IAmYourFriend 0
#define MyFriendsAreYourFriends 1
#define WeAreYourFriends 2
#define WHITE 0
#define BLACK 1
int dsup[100000];
int dsu_p(int x){
return x == dsup[x] ? x : dsup[x] = dsu_p(dsup[x]);
}
void dsu_union(int x,int y){
dsup[dsu_p(y)] = dsu_p(x);
}
int val[100000], color[100000];
vector <int> G[100000];
vector <int> lst[2];
bool visited[100000];
void dfs(int u){
visited[u] = 1;
lst[color[u]].push_back(u);
if (val[dsu_p(u)] < val[u])
swap(val[dsu_p(u)], val[u]);
for(auto v: G[u]){
if (!visited[v])
dfs(v);
}
}
int findSample(int n,int a[],int host[],int type[]){
for(int i=0;i<n;i++)
dsup[i] = i,
val[i] = a[i];
//~ color[0] = WHITE;
for(int i=1;i<n;i++){
G[host[i]].push_back(i);
G[i].push_back(host[i]);
if (type[i] == IAmYourFriend){
color[i] = color[host[i]] ^ 1;
}
else if (type[i] == MyFriendsAreYourFriends){
color[i] = color[host[i]];
}
else{
color[i] = color[host[i]];
dsu_union(i, host[i]);
}
}
int answer = 0;
for(int i=0;i<n;i++){
if (visited[i]) continue;
lst[0].clear();
lst[1].clear();
dfs(i);
int res[2] = {0,0};
for(auto v: lst[0]){
if (dsu_p(v) == v) res[0] += val[v];
}
for(auto v: lst[1]){
if (dsu_p(v) == v) res[1] += val[v];
}
answer += max(res[0], res[1]);
}
return answer;
}
