#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int MAXN = 100100;
int n;
int conf[MAXN], h[MAXN], prot[MAXN];
int sub2 () {
int ret = 0;
FOR(i, 0, n-1) ret += conf[i];
return ret;
}
int sub3 () {
int ret = 0;
FOR(i, 0, n-1) ret = max(ret, conf[i]);
return ret;
}
int dp[MAXN][2];
vi adj[MAXN];
void dfs (int v, int p) {
dp[v][1] = conf[v];
for (int u : adj[v]) {
if (u == p) continue;
dfs (u, v);
dp[v][0] += max(dp[u][0], dp[u][1]);
dp[v][1] += dp[u][0];
}
}
int sub4 () {
FOR(i, 1, n-1) adj[h[i]].pb(i);
dfs (0, -1);
return max(dp[0][1], dp[0][0]);
}
void addE (int u, int v) {
adj[u].pb(v);
adj[v].pb(u);
}
void constructGraph () {
FOR(i, 0, n-1) adj[i].clear();
FOR(i, 1, n-1) {
if (prot[i] == 0) {
addE(h[i], i);
} else if (prot[i] == 1) {
for (int x : adj[h[i]]) {
addE(x, i);
}
} else {
for (int x : adj[h[i]]) {
addE(x, i);
}
addE(h[i], i);
}
}
}
int cnt[2];
bool vis[MAXN];
void bipDfs (int v, bool col = 0) {
cnt[col]++;
vis[v] = true;
for (int u : adj[v])
if (!vis[u])
bipDfs(u, !col);
}
int sub5 () {
constructGraph();
FOR(i, 0, n-1) vis[i] = false;
int ret = 0;
FOR(i, 0, n-1) {
if (vis[i]) continue;
FOR(k, 0, 1) cnt[k] =0 ;
bipDfs(i);
ret += max(cnt[0], cnt[1]);
}
return ret;
}
int findSample(int N,int confidence[],int host[],int protocol[]){
n = N;
FOR(i, 0, n-1) conf[i] = confidence[i];
FOR(i, 1, n-1) h[i] = host[i], prot[i] = protocol[i];
bool is2 = true;
bool is3 = true;
bool is4 = true;
bool is5 = true;
FOR(i, 1, n-1) {
if (protocol[i] != 1) is2 = false;
if (protocol[i] != 2) is3 = false;
if (protocol[i] != 0) is4 = false;
if (protocol[i] == 2) is5 = false;
}
FOR(i, 0, n-1) {
if (conf[i] != 1) is5 = false;
}
if (is2)
return sub2();
else if (is3)
return sub3();
else if (is4)
return sub4();
else if (is5)
return sub5();
else
return sub5();
}
