#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define sz(x) (x.size())
#define pb push_back
#define N 1005
int solve_naive(int n,int confidence[],int host[],int protocol[]) {
int way[15][15]={0};
for(int i=1;i<n;i++) {
if(protocol[i]==1 || protocol[i]==2) {
for(int j=0;j<n;j++) {
if(way[host[i]][j]) {
way[i][j]=way[j][i]=1;
}
}
}
if(protocol[i]==0 || protocol[i]==2) {
way[host[i]][i]=way[i][host[i]]=1;
}
}
int ans=0;
for(int i=0;i<(1<<n);i++) {
vector<int> took;
int tot=0;
for(int j=0;j<n;j++) {
if(i&(1<<j)) {
took.pb(j);
tot+=confidence[j];
}
}
bool flag=true;
for(int j=0;j<sz(took);j++) {
for(int k=0;k<j;k++) {
if(way[took[j]][took[k]]) flag=false;
}
}
if(flag==true) ans=max(ans,tot);
}
return ans;
}
vector<int> v[N];
int dp[2][N];
void dfs(int node,int confidence[]) {
dp[1][node]=confidence[node];
for(int i:v[node]) {
dfs(i,confidence);
dp[1][node]+=dp[0][i];
dp[0][node]+=max(dp[0][i],dp[1][i]);
}
}
int solve_tree(int n,int confidence[],int host[],int protocol[]) {
for(int i=1;i<n;i++) v[host[i]].pb(i);
dfs(0,confidence);
return max(dp[0][0],dp[1][0]);
}
int solve_sum(int n,int confidence[],int host[],int protocol[]) {
int sum=0;
for(int i=0;i<n;i++) sum+=confidence[i];
return sum;
}
int solve_max(int n,int confidence[],int host[],int protocol[]) {
int maxx=0;
for(int i=0;i<n;i++) maxx=max(maxx,confidence[i]);
return maxx;
}
int solve_dsu(int n,int confidence[],int host[],int protocol[]) {
int sum[2]={confidence[0],0};
int reg[N]={0};
for(int i=1;i<n;i++) {
if(protocol[i]==0) {
sum[!reg[host[i]]]+=confidence[i];
reg[i]=!reg[host[i]];
}
else {
sum[reg[host[i]]]+=confidence[i];
reg[i]=reg[host[i]];
}
}
return max(sum[0],sum[1]);
}
int findSample(int n,int confidence[],int host[],int protocol[]) {
if(n<=10) return solve_naive(n,confidence,host,protocol);
bool flag[3]={true,true,true};
bool justone=true;
for(int i=1;i<n;i++) {
justone&=(confidence[i]==1);
for(int j=0;j<3;j++) {
if(j==protocol[i]) flag[j]&=true;
else flag[j]=false;
}
}
if(flag[0]) return solve_tree(n,confidence,host,protocol);
if(flag[1]) return solve_sum(n,confidence,host,protocol);
if(flag[2]) return solve_max(n,confidence,host,protocol);
if(justone) return solve_dsu(n,confidence,host,protocol);
assert(0);
}
