#include "friend.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
// Find out best sample
const int N = 1e5 + 10;
const int Inf = 1e9;
int ty[N], C[N];
vector<int> G[N];
int dp[N][4];
int pd[N], tmp[4];
void DFS(int u){
for(auto adj : G[u])
DFS(adj);
fill(pd, pd + 4, 0);
reverse(G[u].begin(), G[u].end());
for(auto adj : G[u])
{
fill(tmp, tmp + 4, 0);
for(int mkA = 0; mkA < 4; mkA ++)
{
for(int mkD = 0; mkD < 4; mkD ++)
{
if(((mkD & 2) == 2) && ((mkA & 1) == 1)) continue;
tmp[mkA | mkD] = max(tmp[mkA | mkD], dp[adj][mkA] + pd[mkD]);
}
}
for(int i = 0; i < 4; i++) pd[i] = tmp[i];
}
//if(u == 0) cerr << "#### " << pd[2] << '\n';
for(int pi = 0; pi < 2; pi ++)
{
for(int mkD = 0; mkD < 4; mkD ++)
{
if(((mkD & 1) == 1) && (pi == 1)) continue;
int fr = 0, frfr = 0;
if(mkD & 2){
if(ty[u] & 1) fr = 1;
if(ty[u] & 2) frfr = 1;
}
if(pi == 1 && ((ty[u] & 1) == 1)) fr = 1;
if(pi == 1 && ((ty[u] & 2) == 2)) frfr = 1;
dp[u][fr + 2*frfr] = max(dp[u][fr + 2*frfr], pd[mkD] + pi * C[u]);
}
}
}
int findSample(int n, int val[], int par[], int type[]){
for(int i = 1; i < n; i++)
G[par[i]].pb(i);
for(int i = 1; i < n; i++) ty[i] = type[i] + 1;
for(int i = 0; i < n; i++) C[i] = val[i];
DFS(0);
//for(int i = 0; i < 2; i++) for(int j = 0; j < 4; j++) cerr << "! " << i << ' ' << j << " -> " << dp[i][j] << '\n';
return *max_element(dp[0], dp[0] + 4);
}
