// In the name of Allah
#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 4;
const int oo = 1e9 + 7;
int n;
vector<pii> adj[maxn];
int A[maxn], dp[maxn][4][2];
int val[4][2];
void dfs(int v) {
for (int R1 = 0; R1 < 4; R1++) {
for (int R2 = 0; R2 < 2; R2++) {
if (R2 == 0) {
if (!(R1 & 1) && !(R1 & 2)) dp[v][R1][R2] = 0;
else dp[v][R1][R2] = -oo;
}
else {
dp[v][R1][R2] = dp[v][R1][1 - R2];
if (!(R1 & 1) && (R1 & 2)) dp[v][R1][R2] = max(dp[v][R1][R2], A[v]);
}
}
}
for (auto f : adj[v]) {
int u = f.F, op = f.S;
dfs(u);
for (int R1 = 0; R1 < 4; R1++) {
for (int R2 = 0; R2 < 2; R2++) {
val[R1][R2] = dp[v][R1][R2];
}
}
for (int R1 = 0; R1 < 4; R1++) {
for (int R2 = 0; R2 < 2; R2++) {
for (int S1 = 0; S1 < 4; S1++) {
int T1 = 0;
if (S1 & 2) T1 = op;
for (int S2 = 0; S2 < 2; S2++) {
if ((R1 & 1) && (T1 & 2)) continue;
if (R2 == 1 && (T1 & 1)) continue;
val[R1 | T1][R2] = max(val[R1 | T1][R2], dp[v][R1][R2] + dp[u][S1][S2]);
}
}
}
}
for (int R1 = 0; R1 < 4; R1++) {
for (int R2 = 0; R2 < 2; R2++) {
if (R2 == 0) dp[v][R1][R2] = 0;
else dp[v][R1][R2] = dp[v][R1][1 - R2];
dp[v][R1][R2] = max(dp[v][R1][R2], val[R1][R2]);
}
}
}
}
int findSample(int Nx, int ax[], int px[], int opx[]) {
n = Nx;
for (int i = 0; i < n; i++) A[i] = ax[i];
for (int i = 1; i < n; i++) {
int par = px[i], op = opx[i] + 1;
adj[par].pb(Mp(i, op));
}
dfs(0);
int res = -oo;
for (int R1 = 0; R1 < 4; R1++) {
for (int R2 = 0; R2 < 2; R2++) {
res = max(res, dp[0][R1][R2]);
}
}
return res;
}
