#include <bits/stdc++.h>
#include "friend.h"
#pragma GCC optimize("O3")
using namespace std;
int st1(int n, int confidence[], int host[], int protocol[]){
vector<int> g(n);
for(int i = 1; i < n; i++){
if(protocol[i]){
g[i] |= g[host[i]];
for(int j = 0; j < i; j++) if(g[host[i]]&(1<<j)) g[j] |= (1<<i);
}
if(protocol[i] != 1){
g[i] |= (1<<host[i]);
g[host[i]] |= (1<<i);
}
}
int t, s = 0;
for(int i = 0; i < (1<<n); i++){
t = 0;
for(int j = 0; j < n; j++) if(i&(1<<j)) t += confidence[j];
for(int j = 0; j < n; j++) if((i&(1<<j)) && (i&(g[j]))) t = 0;
s = max(s, t);
}
return s;
}
int st2(int n, int confidence[]){
int s = 0;
for(int i = 0; i < n; i++) s += confidence[i];
return s;
}
int st3(int n, int confidence[]){
int mx = 0;
for(int i = 0; i < n; i++) mx = max(mx, confidence[i]);
return mx;
}
void dfs(int u, vector< vector<int> >& g, vector<int>& dp, vector<int>& a){
for(int v : g[u]){
dfs(v, g, dp, a);
a[u] += dp[v];
dp[u] += a[v];
}
dp[u] = max(dp[u], a[u]);
}
int st4(int n, int confidence[], int host[]){
vector< vector<int> > g(n);
vector<int> dp(n), a(n);
for(int i = 1; i < n; i++) g[host[i]].push_back(i);
for(int i = 0; i < n; i++) dp[i] = confidence[i];
dfs(0, g, dp, a);
return dp[0];
}
int bip(int u, vector< vector<int> >& g, vector<int>& vis, int c){
vis[u] = 1;
int r = c;
for(int v : g[u]) if(!vis[v]) r += c^1, bip(v, g, vis, c^1);
return r;
}
int st5(int n, int host[], int protocol[]){
vector< vector<int> > g(n);
for(int i = 1; i < n; i++){
if(protocol[i]){
for(int v : g[host[i]]) g[i].push_back(v), g[v].push_back(i);
}
else{
g[i].push_back(host[i]), g[host[i]].push_back(i);
}
}
int s = 0;
vector<int> vis(n);
for(int i = 0; i < n; i++) if(!vis[i]){
vector<int> temp(n);
s += max(bip(i, g, temp, 0), bip(i, g, vis, 1));
}
return s;
}
int findSample(int n, int confidence[], int host[], int protocol[]){
if(n <= 10) return st1(n, confidence, host, protocol);
for(int i = 2; i < n; i++) if(protocol[i] != protocol[i-1])
return st5(n, host, protocol);
if(protocol[1] == 1) return st2(n, confidence);
if(protocol[1]) return st3(n, confidence);
return st4(n, confidence, host);
}
