#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
int mat[10][10];
vector<int> graph[1005];
int dp[1005][2], C[1005];
void dfs(int u, int p) {
dp[u][1] = C[u];
for(int &v : graph[u]) {
if(v == p) continue;
dfs(v, u);
dp[u][1] += dp[v][0];
dp[u][0] += max(dp[v][0], dp[v][1]);
}
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
int ans=0;
for(int i=0; i<n; i++) C[i] = confidence[i];
if(n <= 10) {
for(int i=1; i<n; i++) {
if(protocol[i] == 0) {
mat[host[i]][i] = mat[i][host[i]] = 1;
} else if(protocol[i] == 1) {
for(int j=0; j<n; j++)
if(mat[host[i]][j]) mat[i][j] = mat[j][i] = 1;
} else {
mat[host[i]][i] = mat[i][host[i]] = 1;
for(int j=0; j<n; j++)
if(mat[host[i]][j]) mat[i][j] = mat[j][i] = 1;
}
}
for(int s=0; s<(1<<n); s++) {
bool ok = 1;
vector<int> vec;
for(int i=0; i<n; i++) {
if(s & (1 << i)) {
for(int &x : vec) if(mat[x][i]) ok = 0;
vec.push_back(i);
}
}
if(ok) {
int sum = 0;
for(int &x : vec) sum += confidence[x];
ans = max(ans, sum);
}
}
return ans;
}
set<int> st;
for(int i=1; i<n; i++) st.insert(protocol[i]);
if(st.size() == 1 && *st.begin() == 1) {
for(int i=0; i<n; i++) ans += confidence[i];
return ans;
}
if(st.size() == 1 && *st.begin() == 2) {
for(int i=0; i<n; i++) ans = max(ans, confidence[i]);
return ans;
}
if(st.size() == 1 && *st.begin() == 0) {
for(int i=1; i<n; i++) {
graph[host[i]].push_back(i);
graph[i].push_back(host[i]);
}
dfs(0, 0);
return max(dp[0][0], dp[1][0]);
}
return ans;
}
