#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int N = 1e5 + 10;
int ty[N] , n , ar[N] , dp[N][2];
vector <int> adj[N];
void Dfs(int v)
{
for(auto u : adj[v])
Dfs(u);
if(adj[v].empty())
{
dp[v][0] = 0;
dp[v][1] = ar[v];
}
int tmp[2];
tmp[0] = 0;
tmp[1] = ar[v];
for(int i = adj[v].size() - 1 ; i >= 0 ; i--)
{
auto u = adj[v][i];
if(ty[u] == 1)
{
tmp[0] += dp[u][1];
tmp[1] = max(tmp[0] , tmp[1] + dp[u][0]);
}
else if(ty[u] == 2)
{
tmp[0] += dp[u][0];
tmp[1] += dp[u][1];
}
else
{
tmp[1] = max(tmp[0] + dp[u][1] , tmp[1] + dp[u][0]);
tmp[0] += dp[u][0];
}
}
dp[v][0] = tmp[0];
dp[v][1] = tmp[1];
}
int findSample(int nn , int confidence[] , int host[] , int protocol[]){
n = nn;
for(int i = 0 ; i < n ; i++)
ar[i] = confidence[i];
for(int i = 1 ; i < n ; i++)
{
adj[host[i]].push_back(i);
ty[i] = protocol[i] + 1;
}
Dfs(0);
return dp[0][1];
}
