#include "friend.h"
//#include "grader.cpp"
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1015;
int n;
vector <int> graph[MAXN];
void constructGrahp(int n, int confidence[], int host[], int protocol[])
{
for(int x = 1;x<=n;x++)
{
if(protocol[x]==0)
{
graph[ host[x] ].push_back(x);
graph[x].push_back(host[x]);
}
else if(protocol[x]==1)
{
for(int y: graph[ host[x] ])
{
graph[y].push_back(x);
graph[x].push_back(y);
}
}
else if(protocol[x]==2)
{
graph[x].push_back(host[x]);
graph[ host[x] ].push_back(x);
for(int y: graph[ host[x] ])
{
graph[y].push_back(x);
graph[x].push_back(y);
}
}
}
}
namespace Subtask1
{
bool can(int x, int mask)
{
for(int y: graph[x])
{
if(((mask>>y)&1)==1) return false;
}
return true;
}
int rec(int x, int mask, int confidence[])
{
if(x==n) return 0;
int answer = rec(x+1, mask, confidence);
if(can(x, mask)==true) answer = max(answer, confidence[x]+rec(x+1, (mask|(1<<x)), confidence));
return answer;
}
int solve(int n, int confidence[], int host[], int protocol[])
{
constructGrahp(n, confidence, host, protocol);
return rec(0, 0, confidence);
}
};
namespace Subtask2
{
int solve(int n, int confidence[], int host[], int protocol[])
{
int ans = 0;
for(int x = 0;x<n;x++) ans += confidence[x];
return ans;
}
};
namespace Subtask3
{
int solve(int n, int confidence[], int host[], int protocol[])
{
int ans = 0;
for(int x = 0;x<n;x++) ans = max(ans, confidence[x]);
return ans;
}
};
namespace Subtask4
{
int memo[MAXN][2];
int rec(int x, int last, bool take, int confidence[])
{
if(memo[x][take]!=-1)
return memo[x][take];
int answer = 0;
if(take==true)
{
answer += confidence[x];
for(int y: graph[x])
{
if(y==last) continue;
answer += rec(y, x, false, confidence);
}
}
else
{
for(int y: graph[x])
{
if(y==last) continue;
answer += max(rec(y, x, true, confidence), rec(y, x, false, confidence));
}
}
memo[x][take] = answer;
return answer;
}
int solve(int n, int confidence[], int host[], int protocol[])
{
memset(memo, -1, sizeof(memo));
constructGrahp(n, confidence, host, protocol);
return max(rec(0, -1, false, confidence), rec(0, -1, true, confidence));
}
};
namespace Subtask5
{
struct MaxFlowGraph
{
int S, T;
int dist[MAXN], ind[MAXN];
vector <int> edges;
vector <pair <int, int>> graph[MAXN];
MaxFlowGraph(){}
MaxFlowGraph(int S, int T)
{
this->S = S;
this->T = T;
}
void addEdge(int u, int v, int cap)
{
//cout << u << " -> " << v << '\n';
//cout << u << " " << v << '\n';
graph[u].push_back({v, edges.size()});
edges.push_back(cap);
graph[v].push_back({u, edges.size()});
edges.push_back(0);
}
void bfs(int x)
{
memset(dist, -1, sizeof(dist));
queue <int> q;
dist[x] = 0;
q.push(x);
while(q.empty()==false)
{
x = q.front();
q.pop();
for(pair <int, int> y: graph[x])
{
if(dist[y.first]==-1 && edges[y.second]>0)
{
dist[y.first] = dist[x] + 1;
q.push(y.first);
}
}
}
}
int dfs(int x, int minEdge)
{
if(x==T) return minEdge;
for(int i = ind[x];i<graph[x].size();i++)
{
if(dist[ graph[x][i].first ]==dist[x]+1 && edges[ graph[x][i].second ]>0)
{
int flow = dfs(graph[x][i].first, min(minEdge, edges[ graph[x][i].second ]));
if(flow!=-1)
{
edges[ graph[x][i].second ] -= flow;
edges[ graph[x][i].second^1 ] += flow;
return flow;
}
}
//ind[x]++;
}
return -1;
}
int Dinic()
{
int flow = 0;
while(true)
{
bfs(S);
if(dist[T]==-1) break;
memset(ind, 0, sizeof(ind));
while(true)
{
int add = dfs(S, 1);
if(add==-1) break;
flow += add;
}
}
return flow;
}
};
int color[MAXN];
void dfsColor(int x, int col, MaxFlowGraph &G)
{
color[x] = col + 1;
for(int y: graph[x])
{
if(color[y]==0)
{
dfsColor(y, col^1, G);
}
}
}
int solve(int n, int confidence[], int host[], int protocol[])
{
constructGrahp(n, confidence, host, protocol);
int S = n, T = n + 1;
MaxFlowGraph G(S, T);
vector <pair <int, int>> all;
for(int x = 1;x<n;x++)
{
if(protocol[x]==0)
{
all.push_back({host[x], x});
graph[x].push_back(host[x]);
graph[ host[x] ].push_back(x);
//G.addEdge(host[x], x, 1);
}
else
{
for(int y: graph[ host[x] ])
{
all.push_back({y, x});
graph[x].push_back(y);
graph[y].push_back(x);
//G.addEdge(y.first, x, 1);
}
}
}
for(int x = 0;x<n;x++)
{
if(color[x]==0) dfsColor(x, 0, G);
}
for(pair <int, int> x: all)
{
int u = x.first;
int v = x.second;
if(color[u]>color[v]) swap(u, v);
G.addEdge(u, v, 1);
}
for(int x = 0;x<n;x++)
{
if(color[x]==1) G.addEdge(S, x, 1);
else G.addEdge(x, T, 1);
}
//cout << "K" << '\n';
return n - G.Dinic();
}
};
int guessSubtask(int n, int confidence[], int host[], int protocol[])
{
if(n<=10) return 1;
bool subtask2 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]!=1)
{
subtask2 = false;
break;
}
}
if(subtask2==true) return 2;
bool subtask3 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]!=2)
{
subtask3 = false;
break;
}
}
if(subtask3==true) return 3;
bool subtask4 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]!=0)
{
subtask4 = false;
break;
}
}
if(subtask4==true) return 4;
bool subtask5 = true;
for(int x = 1;x<n;x++)
{
if(protocol[x]==2)
{
subtask5 = false;
break;
}
}
if(subtask5==true) return 5;
return -1;
}
int findSample(int _n,int confidence[],int host[],int protocol[])
{
n = _n;
int subtask = 5;//guessSubtask(n, confidence, host, protocol);
if(subtask==2) return Subtask2::solve(n, confidence, host, protocol);
if(subtask==3) return Subtask3::solve(n, confidence, host, protocol);
if(subtask==1) return Subtask1::solve(n, confidence, host, protocol);
if(subtask==4) return Subtask4::solve(n, confidence, host, protocol);
if(subtask==5) return Subtask5::solve(n, confidence, host, protocol);
return 0;
}
