#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
set<int> adj[MAXN];
vector<int> CONF;
int dfs(int u, int p = -1, bool count = true) {
int ans = 0;
if (count) ans = CONF[u];
for (auto v: adj[u]) {
if (v == p) continue;
ans += dfs(v, u, !count);
}
return ans;
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[]){
CONF.clear();
for (int i = 0; i < n; i++) CONF.push_back(confidence[i]);
int hist[3] = {0, 0, 0};
int sum = 0;
int maxi = 0;
for (int i = 0; i < n; i++) {
sum += confidence[i];
maxi = max(maxi, confidence[i]);
if (i == 0) continue;
hist[protocol[i]]++;
}
if (hist[0] == 0 && hist[2] == 0) {
return sum;
}
if (hist[0] == 0 && hist[1] == 0) {
return maxi;
}
if (hist[2] == 0) {
int ans = 0;
for (int i = n - 1; i > 0; i--) {
int h = host[i];
if (protocol[i] == 1) confidence[h] += confidence[i];
else {
if (confidence[i] > confidence[h]) {
ans += confidence[i];
confidence[h] = 0;
} else {
confidence[h] -= confidence[i];
ans += confidence[i];
confidence[i] = 0;
}
}
}
return ans + confidence[0];
}
for (int i = 0; i < n; i++) {
if (i == 0) continue;
int h = host[i];
switch (protocol[i]) {
case 0:
// I am your friend
adj[h].insert(i);
adj[i].insert(h);
break;
case 1:
// my friends are your friends
for (int f: adj[h]) {
adj[i].insert(f);
adj[f].insert(i);
}
break;
case 2:
// we are your friends
adj[h].insert(i);
adj[i].insert(h);
for (int f: adj[h]) {
adj[i].insert(f);
adj[f].insert(i);
}
break;
}
}
// a friend can't be a friend of themselves
for (int i = 0; i < n; i++) adj[i].erase(i);
// for (int i = 0; i < n; i++) {
// cerr << i << ": ";
// for (auto x: adj[i]) cerr << x << " ";
// cerr << endl;
// }
if (n <= 10) {
int max_ans = 0;
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
set<int> s;
for (int j = 0; j < n; j++)
if (i & (1 << j)) s.insert(j);
bool ok = true;
for (auto x: s)
for (auto f: adj[x])
if (s.count(f)) {
ok = false;
break;
}
if (!ok) continue;
for (auto x: s) ans += confidence[x];
max_ans = max(max_ans, ans);
ans = 0;
}
return max_ans;
}
return 0;
}
