// ~ Be Name Khoda ~ //
#include "friend.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 5e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int cmp[maxn5], hs[maxn5], ty[maxn5];
ll val[maxn5];
int n, dp[maxn5][2], mat[maxn5];
vector <int> adj[maxn5];
bool mark[maxn5];
int sub1(){
for(int i = 1; i < n; i++){
if(ty[i] == 0){
adj[i].pb(hs[i]);
adj[hs[i]].pb(i);
}
else if(ty[i] == 1){
for(auto u : adj[hs[i]]){
adj[i].pb(u);
adj[u].pb(i);
}
}
else{
for(auto u : adj[hs[i]]){
adj[i].pb(u);
adj[u].pb(i);
}
adj[hs[i]].pb(i);
adj[i].pb(hs[i]);
}
}
int ans = 0;
for(int mask = 1; mask < (1 << n); mask++){
bool re = true;
for(int i = 0; i < n; i++) if((mask >> i)&1)
for(auto u : adj[i]) if((mask >> u)&1)
re = false;
if(re){
int sum = 0;
for(int i = 0; i < n; i++) if((mask >> i)&1)
sum += val[i];
ans = max(ans, sum);
}
}
return ans;
}
int sub2(){
ll sum = 0;
for(int i = 0; i < n; i++)
sum += val[i];
return sum;
}
int sub3(){
ll mx = 0;
for(int i = 0; i < n; i++)
mx = max(mx, val[i]);
return mx;
}
void dfs4(int v){
dp[v][1] = val[v];
for(auto u : adj[v]){
dfs4(u);
dp[v][0] += max(dp[u][0], dp[u][1]);
dp[v][1] += dp[u][0];
}
}
int sub4(){
for(int i = 1; i < n; i++)
adj[hs[i]].pb(i);
dfs4(0);
return max(dp[0][0], dp[0][1]);
}
bool dfs5(int v){
mark[v] = true;
for(auto u : adj[v]) if(mat[u] == -1 || (!mark[mat[u]] && dfs5(mat[u]))){
mat[v] = u;
mat[u] = v;
return true;
}
return false;
}
int sub5(){
for(int i = 1; i < n; i++){
cmp[i] = cmp[hs[i]] ^ ty[i] ^ 1;
if(ty[i] == 0){
adj[i].pb(hs[i]);
adj[hs[i]].pb(i);
}
else{
for(auto u : adj[hs[i]]){
adj[i].pb(u);
adj[u].pb(i);
}
}
}
bool con = true;
memset(mat, -1, sizeof mat);
int ans = 0;
while(con){
con = false;
memset(mark, false, sizeof mark);
for(int i = 0; i < n; i++) if(!mark[i] && cmp[i] && mat[i] == -1 && dfs5(i)){
con = true;
ans++;
}
}
return n - ans;
}
// Find out best sample
int findSample(int n,int confidence[], int host[], int protocol[]){
::n = n;
for(int i = 1; i < n; i++){
val[i] = confidence[i];
hs[i] = host[i];
ty[i] = protocol[i];
}
val[0] = confidence[0];
if(n <= 10)
return sub1();
bool ok = true;
for(int i = 1; i < n; i++)
ok &= (protocol[i] == protocol[1]);
if(ok){
if(protocol[1] == 0)
return sub4();
if(protocol[1] == 1)
return sub2();
return sub3();
}
return sub5();
}
