#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int sub1 (int n, int confidence[], int host[], int protocol[]) {
bool friends[n][n];
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
friends[i][j] = 0;
}
}
for (int i = 1;i < n;i++) {
if (protocol[i] == 0) {
friends[host[i]][i] = true;
friends[i][host[i]] = true;
}
if (protocol[i] == 1) {
for (int j = 0;j <= n;j++) {
if (friends[host[i]][j] == true) {
friends[j][i] = true;
friends[i][j] = true;
}
}
}
if (protocol[i] == 2) {
friends[host[i]][i] = true;
friends[i][host[i]] = true;
for (int j = 0;j <= n;j++) {
if (friends[host[i]][j] == true) {
friends[j][i] = true;
friends[i][j] = true;
}
}
}
}
// for (int i = 0;i < n;i++) {
// for (int j = 0;j < n;j++) {
// cout << friends[i][j];
// }
// cout << endl;
// }
//check
int k = (1 << n);
int ans = 0;
for (int i = 0;i < k;i++) {
int res = 0;
vector <int> v;
for (int j = 0;j < n;j++) {
if (((1 << j) & i)) {
v.push_back(j);
res += confidence[j];
}
}
bool pos = true;
for (int j = 0;j < v.size();j++) {
for (int l = j + 1;l < v.size();l++) {
if (friends[v[j]][v[l]] == true) {
pos = false;
break;
}
}
}
if (pos) {
ans = max(ans, res);
}
}
return ans;
}
int sub2 (int n, int confidence[], int host[], int protocol[]) {
int ans = 0;
for (int i = 0;i < n;i++) {
ans += confidence[i];
}
return ans;
}
int sub3 (int n, int confidence[], int host[], int protocol[]) {
int ans = 0;
for (int i = 0;i < n;i++) {
ans = max(ans, confidence[i]);
}
return ans;
}
vector <vector <int>> adj;
vector <array<int, 2>> dp;
vector <int> conf;
void dfs(int u, int p) {
dp[u][1] = conf[u];
for (auto v : adj[u]) {
if (v == p) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int sub4 (int n, int confidence[], int host[], int protocol[]) {
adj.resize(n);
dp.resize(n, {0, 0});
conf.resize(n);
for (int i = 0;i < n;i++) conf[i] = confidence[i];
for (int i = 1;i < n;i++) {
adj[host[i]].push_back(i);
adj[i].push_back(host[i]);
}
dfs(0, -1);
return max(dp[0][0], dp[0][1]);
}
int findSample(int n, int confidence[], int host[], int protocol[]){
int ans = 10;
int prot = -1;
for (int i = 1;i < n;i++) {
if (prot == -1) {
prot = protocol[i];
}
if (prot != protocol[i]) {
prot = -2;
}
}
if (n <= 10) {
return sub1(n, confidence, host, protocol);
}
if (prot == 0) {
return sub4(n, confidence, host, protocol);
}
if (prot == 1) {
return sub2(n, confidence, host, protocol);
}
if (prot == 2) {
return sub3(n, confidence, host, protocol);
}
if (prot == -2) return 0;
return ans;
}
