#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=b;a<c;a++)
#define F first
#define S second
#define PB push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
vii a;
int n;
vi prt,hst,c,p;
vii dp;
int brute(int confidence[]){
int m=pow(2,n);
int ans=0;
REP(i,0,n)sort(a[i].begin(),a[i].end());
REP(i,1,m){
int k=0;
set<int> st;
REP(j,0,n){
if(i&(1<<j))st.insert(j);
}
bool flag=1;
for(auto u:st){
for(auto v:a[u]){
if(st.count(v)!=0)flag=0;
}
}
for(auto u:st)k+=confidence[u];
if(flag)ans=max(ans,k);
}
return ans;
}
void solve(int x){
int mx=0,mx2=0;
for(auto u:a[x])if(p[x]!=u){
p[u]=x;
solve(u);
mx+=max(dp[u][0],dp[u][1]);
mx2+=dp[u][0];
}
dp[x][1]+=mx2;
dp[x][0]+=mx;
}
// Find out best sample
int findSample(int N,int confidence[],int host[],int protocol[]){
n=N;
prt.resize(n);hst.resize(n);c.resize(n);
REP(i,1,n)hst[i]=host[i];
REP(i,1,n)prt[i]=protocol[i];
REP(i,0,n)c[i]=confidence[i];
bool flag=1,flag2=1,flag3=1;
REP(i,1,n)if(prt[i]!=2)flag=0;
REP(i,1,n)if(prt[i]!=1)flag2=0;
REP(i,1,n)if(prt[i]!=0)flag3=0;
if(flag)return *max_element(confidence,confidence+n);
int sm=0;
REP(i,0,n)sm+=c[i];
if(flag2)return sm;
a.resize(n);
REP(i,1,n){
int pos=host[i];
if(protocol[i]==0||protocol[i]==2){
a[pos].PB(i);
a[i].PB(pos);
}
if(protocol[i]==1||protocol[i]==2){
for(auto u:a[pos])if(u!=i){
a[u].PB(i);
a[i].PB(u);
}
}
}
if(n<=10)return brute(confidence);
if(flag3){
p.resize(n,-1);dp.resize(n,vi(2));
REP(i,0,n)dp[i][1]=c[i];
REP(i,0,n)dp[i][0]=0;
solve(0);
return max(dp[0][0],dp[0][1]);
}
vi t(n,-1);
int k=0;
REP(i,0,n){
if(t[i]!=-1)continue;
queue<int> pq;
pq.push(i);
t[i]=k;
while(!pq.empty()){
int x=pq.front();
pq.pop();
for(auto u:a[x])if(t[u]==-1){
t[u]=k;
if(t[x]==k)t[u]++;
pq.push(u);
}
}
k+=2;
}
int ans=0;
REP(i,0,k){
int sm=0,sm2=0;
REP(j,0,n)if(t[j]==i)sm+=c[j];
REP(j,0,n)if(t[j]==i+1)sm2+=c[j];
ans+=max(sm,sm2);
i++;
}
return ans;
}
