#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
vector<pair<int, int>> chef;
vector<set<int>> graph;
void init(int n, int values[]) {
chef.clear();
chef.resize(n);
for (int i = 0; i<n; i++) {
chef[i].first = i;
chef[i].second = values[i];
}
graph.clear();
graph.resize(n);
}
int find(int x) {
if (chef[x].first == x) return x;
return chef[x].first = find(chef[x].first);
}
void unite(int a, int b, bool addup) {
if (find(a) == find(b)) return;
if (graph[a].size() > graph[b].size()) swap(graph[a], graph[b]);
for (int i: graph[find(a)]) {
graph[find(b)].insert(i);
}
if (addup) chef[find(b)].second += chef[find(a)].second;
else chef[find(b)].second = max(chef[find(b)].second, chef[find(a)].second);
chef[find(a)].first = find(b);
}
pair<int, int> dfs(int v, vector<bool> &visited, vector<int> &val) {
v = find(v);
if (visited[v]) return {0, 0};
visited[v] = 1;
pair<int, int> res = {chef[find(v)].second, 0};
for (int i: graph[v]) {
pair<int, int> tmp = dfs(i, visited, val);
res.first += tmp.second;
res.second += tmp.first;
}
res.first = max(res.first, res.second);
return res;
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
init(n, confidence);
for (int i = 1; i<n; i++) {
if (protocol[i] == 0) {
graph[find(host[i])].insert(find(i));
graph[find(i)].insert(find(host[i]));
}
if (protocol[i] == 1) {
for (int j: graph[find(host[i])]) {
unite(*graph[find(host[i])].begin(), j, 1);
}
if (graph[find(host[i])].empty()) continue;
graph[find(*graph[find(host[i])].begin())].insert(find(i));
graph[find(i)].insert(find(*graph[find(host[i])].begin()));
}
if (protocol[i] == 2) {
for (int j: graph[find(host[i])]) {
unite(*graph[find(host[i])].begin(), j, 1);
}
unite(i, host[i], 0);
if (graph[find(host[i])].empty()) continue;
graph[find(*graph[find(host[i])].begin())].insert(find(i));
graph[find(i)].insert(find(*graph[find(host[i])].begin()));
}
}
vector<bool> visited(n, 0);
vector<int> values;
for (int i = 0; i<n; i++) values.push_back(confidence[i]);
int res = 0;
for (int i = 0; i<n; i++) res += dfs(i, visited, values).first;
return res;
}
