#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
int N, sol;
int A[1000];
vector <int> VG[1000];
inline void Sub1()
{
if(N > 10) return;
for(int i = 1; i < (1 << N); i++)
{
int temp = 0;
for(int j = 0; (j < N) && (temp >= 0); j++)
{
if(!(i & (1 << j))) continue;
temp += A[j];
for(int x : VG[j]) if(i & (1 << x)) temp = -1;
}
sol = max(temp, sol);
}
return;
}
inline void Sub2(int t[])
{
bool flag = true;
for(int i = 1; i < N; i++) flag &= t[i] == 1;
if(!flag) return;
sol = 0;
for(int i = 0; i < N; i++) sol += A[i];
return;
}
inline void Sub3(int t[])
{
bool flag = true;
for(int i = 1; i < N; i++) flag &= t[i] == 2;
if(!flag) return;
sol = 0;
for(int i = 0; i < N; i++) sol = max(A[i], sol);
return;
}
int DP[2][1000];
inline void DPDFS(int node, int parent = -1)
{
for(int x : VG[node]) if(x != parent) DPDFS(x, node);
DP[0][node] = 0;
for(int x : VG[node]) DP[0][node] += (x != parent) * max(DP[0][x], DP[1][x]);
DP[1][node] = A[node];
for(int x : VG[node]) DP[1][node] += (x != parent) * DP[0][x];
return;
}
inline void Sub4(int t[])
{
bool flag = true;
for(int i = 1; i < N; i++) flag &= t[i] == 0;
if(!flag) return;
DPDFS(0);
sol = max(DP[0][0], DP[1][0]);
return;
}
int cnt[2], V[1000];
inline void DFS(int node)
{
cnt[V[node]]++;
for(int x : VG[node]) if(V[x] < 0) {V[x] = V[node] ^ 1; DFS(x);}
return;
}
inline void Sub5(int t[])
{
bool flag = true;
for(int i = 0; i < N; i++) flag &= A[i] == 1;
for(int i = 1; i < N; i++) flag &= t[i] != 2;
if(!flag) return;
sol = 0;
for(int i = 0; i < N; i++) V[i] = -1;
for(int i = 0; i < N; i++)
{
if(V[i] >= 0) continue;
V[i] = cnt[0] = cnt[1] = 0;
DFS(i);
sol += max(cnt[0], cnt[1]);
}
return;
}
int findSample(int n, int a[], int p[], int t[])
{
if(n > 1000) return 0;
N = n;
for(int i = 0; i < N; i++) A[i] = a[i];
for(int i = 1; i < N; i++)
{
if(t[i] != 0) for(int x : VG[p[i]]) {VG[x].push_back(i); VG[i].push_back(x);}
if(t[i] != 1) {VG[p[i]].push_back(i); VG[i].push_back(p[i]);}
}
Sub1();
Sub2(t);
Sub3(t);
Sub4(t);
Sub5(t);
return sol;
}
