#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int MAX_N = 1e5 + 5;
int N, C[MAX_N];
int dp[MAX_N][2];
vector <int> graph[MAX_N];
bool visited[MAX_N];
void dfs(int u) {
dp[u][1] = C[u];
for(auto v : graph[u]) {
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
}
for(auto v : graph[u]) {
dp[u][1] = max(dp[u][1], dp[u][0] - max(dp[v][0], dp[v][1]) + dp[v][0] + C[u]);
}
}
void connect(int s, int x) {
fill(visited, visited + N, false);
queue <int> q;
q.push(s);
visited[s] = true;
vector <int> need;
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto v : graph[u]) {
if(visited[v] == false) {
visited[v] = true;
need.push_back(v);
q.push(v);
}
}
}
for(auto v : need) {
graph[v].push_back(x);
graph[x].push_back(v);
}
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]){
N = n;
int cnt[3] = {};
for(int i = 0; i < n; i++) {
C[i] = confidence[i];
}
for(int i = 1; i < n; i++) {
cnt[protocol[i]]++;
}
int ans = 0;
if(n <= 10) {
for(int i = 1; i < n; i++) {
if(protocol[i] == 0) {
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
else if(protocol[i] == 1) {
connect(host[i], i);
}
else if(protocol[i] == 2) {
connect(host[i], i);
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
}
for(int mask = 0; mask < (1<<n); mask++) {
set <int> consider;
int sum = 0;
for(int i = 0; i < n; i++) {
if(mask & (1<<i)) {
sum += C[i];
consider.insert(i);
}
}
for(auto u : consider) {
for(auto v : graph[u]) {
if(consider.count(v)) {
sum = 0;
}
}
}
ans = max(ans, sum);
}
}
else if(cnt[0] == n) {
for(int i = 1; i < n; i++) {
graph[host[i]].push_back(i);
}
dfs(0);
ans = max(dp[0][0], dp[0][1]);
}
else if(cnt[1] == n) {
for(int i = 0; i < n; i++) {
ans += confidence[i];
}
}
else if(cnt[2] == n) {
for(int i = 0; i < n; i++) {
ans = max(ans, confidence[i]);
}
}
else {
// do something
}
return ans;
}
