#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
struct MaxFlow{
struct Edge{
int from , to , flow , cap;
};
int s , t;
vector<int> ptr , dist;
vector<Edge> E;
vector<vector<int>> adj;
queue<int> Q;
void init(int n){
E.clear(); adj.clear(); ptr.clear(); dist.clear();
adj.resize(n); ptr.resize(n); dist.resize(n);
}
void add(int v , int u , int cap){
adj[v].push_back(SZ(E)); E.push_back({v , u , 0 , cap});
adj[u].push_back(SZ(E)); E.push_back({u , v , 0 , 0});
}
int BFS(){
fill(all(dist) , MOD);
fill(all(ptr) , 0);
dist[s] = 0;
queue<int> q; q.push(s);
while(!q.empty()){
int v = q.front(); q.pop();
for(int i : adj[v]){
int u = E[i].to;
if(E[i].flow == E[i].cap) continue;
if(dist[u] == MOD){
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
return (dist[t] < MOD);
}
int DFS(int v , int w){
if(v == t) return w;
int ans = 0;
for( ; ptr[v] < SZ(adj[v]) ; ptr[v]++){
int ind = adj[v][ptr[v]] , u = E[ind].to;
if(E[ind].flow == E[ind].cap || dist[u] != dist[v] + 1) continue;
int cur = min(w - ans , E[ind].cap - E[ind].flow);
int val = DFS(u , cur);
ans += val; E[ind].flow += val; E[ind ^ 1].flow -= val;
if(ans == w) break;
}
return ans;
}
int flow(int v , int u){
s = v; t = u; int ans = 0;
while(BFS()) ans += DFS(s , MOD);
return ans;
}
} flow;
int col[MAXN];
vector<int> adj[MAXN];
int findSample(int n,int confidence[],int host[],int protocol[]){
/*flow.init(10);
flow.add(0 , 1 , 10);
flow.add(0 , 2 , 10);
flow.add(1 , 3 , 10);
flow.add(2 , 3 , 7);
flow.add(3 , 4 , 8);
cout << flow.flow(0 , 4) << endl;*/
int mx = 0 , sum = 0 , flag = 0;
for(int i = 0 ; i < n ; i++){
sum += confidence[i];
mx = max(mx , confidence[i]);
}
for(int i = 1 ; i < n ; i++){
protocol[i]++;
if(protocol[i] & 2){
for(int j : adj[host[i]]){
adj[i].push_back(j);
adj[j].push_back(i);
}
col[i] = col[host[i]];
}
if(protocol[i] & 1){
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
col[i] = (col[host[i]] ^ 1);
}
if(protocol[i] == 3){
flag = 1;
}
}
if(flag) return mx;
flow.init(n + 2);
for(int i = 0 ; i < n ; i++){
if(col[i] == 0){
flow.add(0 , i + 1 , confidence[i]);
for(int j : adj[i]) flow.add(i + 1 , j + 1 , MOD);
}
else flow.add(i + 1 , n + 1 , confidence[i]);
}
return sum - flow.flow(0 , n + 1);
}
