#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
vector < int > adj[MAXN];
int dp[MAXN][2];
bool visited[MAXN];
void build_graph(int n, int p[], int type[])
{
for(int i = 1; i < n; i++)
{
if(type[i] == 0)
{
adj[i].push_back(p[i]);
adj[p[i]].push_back(i);
}
else if(type[i] == 1)
{
for(int v : adj[p[i]])
{
adj[v].push_back(i);
adj[i].push_back(v);
}
}
else if(type[i] == 2)
{
for(int v : adj[p[i]])
{
adj[v].push_back(i);
adj[i].push_back(v);
}
adj[i].push_back(p[i]);
adj[p[i]].push_back(i);
}
}
}
int bruteforce(int n, int c[])
{
int ans = 0;
for(int mask = 1; mask < (1 << n); mask++)
{
bool lampa = false;
for(int i = 0; i < n; i++)
{
if(mask & (1 << i))
{
for(int v : adj[i])
{
if(mask & (1 << v))
lampa = true;
}
}
}
if(lampa)
continue;
int sum = 0;
for(int i = 0; i < n; i++)
{
if(mask & (1 << i))
sum += c[i];
}
ans = max(ans, sum);
}
return ans;
}
void dfs(int u, int par, int c[])
{
visited[u] = true;
dp[u][1] = c[u];
for(int v : adj[u])
{
if(v == par)
continue;
dfs(v, u, c);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int solve_dp(int n, int c[])
{
int ans = 0;
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
dfs(i, i, c);
ans += max(dp[i][0], dp[i][1]);
}
}
return ans;
}
int findSample(int n, int c[], int p[], int type[])
{
build_graph(n, p, type);
if(n <= 10)
return bruteforce(n, c);
else
return solve_dp(n, c);
}
