#include <bits/stdc++.h>
using namespace std;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
template <typename T>
bool chmin(T &lhs, const T &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <typename T>
bool chmax(T &lhs, const T &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;
template <typename T>
void trc(const Vec<T> &a) {
cerr << "[";
REP(i, a.size()) {
if (i > 0) {
cerr << ", ";
}
cerr << a[i];
}
cerr << "]\n";
}
constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003LL;
struct DP {
i32 tw;
array<i64, 3> nosp;
array<array<array<i64, 3>, 3>, 2> sp;
DP() : tw(0), nosp(), sp() {
REP(i, 3) {
nosp[i] = INF64;
}
REP(i, 2) REP(j, 3) REP(k, 3) {
sp[i][j][k] = INF64;
}
}
};
bool is_ok(i64 lw, i64 lst, i64 rst) {
if (lst == 2 || rst == 2) {
return true;
}
if (lw) {
rst ^= 1;
}
return lst == rst;
}
array<i64, 3> merge_not_free(array<i64, 3> l, array<i64, 3> r, i32 lw) {
if (lw) {
swap(r[0], r[1]);
}
array<i64, 3> ret;
ret[0] = min({l[2] + r[0], l[0] + r[2], l[0] + r[0]});
ret[1] = min({l[2] + r[1], l[1] + r[2], l[1] + r[1]});
ret[2] = l[2] + r[2];
return ret;
}
DP merge(const DP &l, const DP &r, i64 w) {
DP ret;
ret.tw = l.tw ^ r.tw;
ret.nosp = merge_not_free(l.nosp, r.nosp, l.tw);
REP(ll, 3) REP(rr, 3) {
chmin(ret.sp[r.tw][ll][rr], l.nosp[ll] + r.nosp[rr] + w);
}
REP(lw, 2) REP(ll, 3) REP(lr, 3) REP(rr, 3) REP(whe, 2) {
i64 cost = l.sp[lw][ll][lr] + r.nosp[rr];
if (whe) {
cost += w;
chmin(ret.sp[r.tw][ll][rr], cost);
} else if (rr == 2) {
chmin(ret.sp[lw ^ r.tw][ll][lr], cost);
} else if (lr == 2) {
chmin(ret.sp[lw ^ r.tw][ll][rr ^ lw], cost);
} else if ((lr ^ lw) == rr) {
chmin(ret.sp[lw ^ r.tw][ll][lr], cost);
}
}
REP(lr, 3) REP(rw, 2) REP(rl, 3) REP(rr, 3) REP(whe, 2) {
i64 cost = l.nosp[lr] + r.sp[rw][rl][rr];
if (whe) {
cost += w;
chmin(ret.sp[r.tw][lr][rr], cost);
} else if (rl == 2) {
chmin(ret.sp[rw][lr][rr], cost);
} else if (lr == 2) {
chmin(ret.sp[rw][rw ^ l.tw][rr], cost);
} else if ((lr ^ l.tw) == rl) {
chmin(ret.sp[rw][lr][rr], cost);
}
}
REP(lw, 2) REP(ll, 3) REP(lr, 3) REP(rw, 2) REP(rl, 3) REP(rr, 3) {
i64 cost = l.sp[lw][ll][lr] + r.sp[rw][rl][rr];
if (!is_ok(lw, lr, rl)) {
cost += w;
}
chmin(ret.sp[rw][ll][rr], cost);
}
return ret;
}
DP trans(const DP &dp, i64 c) {
DP ret = dp;
chmin(ret.nosp[2], ret.nosp[0] + c);
chmin(ret.nosp[2], ret.nosp[1] + c);
REP(w, 2) REP(l, 3) REP(r, 3) {
chmin(ret.sp[w][2][2], ret.sp[w][l][r] + c);
}
return ret;
}
i64 place_police(Vec<i32> p, Vec<i64> c, Vec<i64> w) {
p.insert(p.begin(), 0);
c.insert(c.begin(), 0);
i32 n = (i32)p.size();
Vec<Vec<pair<i32, i64>>> chl(n);
REP(i, 1, n) {
chl[p[i]].emplace_back(i, c[i]);
}
Vec<i32> dep(n, 0);
Vec<i32> rch(n, 0);
i32 chc = 0;
REP(i, n) {
for (auto [ch, _] : chl[i]) {
dep[ch] = dep[i] + 1;
}
if (chl[i].empty()) {
rch[i] = chc++;
}
}
PER(i, n) {
if (!chl[i].empty()) {
rch[i] = rch[chl[i].back().first];
}
}
Vec<DP> dp(n);
PER(i, n) {
if (chl[i].empty()) {
dp[i].tw = 1;
dp[i].nosp[dep[i] % 2] = 0;
} else {
Vec<DP> lst;
lst.reserve(chl[i].size());
for (auto [ch, cost] : chl[i]) {
lst.push_back(trans(dp[ch], cost));
}
dp[i] = lst.front();
REP(j, 1, lst.size()) {
dp[i] = merge(dp[i], lst[j], w[rch[chl[i][j - 1].first]]);
/* REP(x, 3) {
cerr << dp[i].nosp[x] << " \n"[x == 2];
}
REP(x, 2) REP(y, 3) REP(z, 3) {
cerr << dp[0].sp[x][y][z] << " \n"[z == 2];
}
*/
}
}
}
i64 ans = INF64;
if (w.size() % 2 == 0) {
chmin(ans, dp[0].nosp[0]);
chmin(ans, dp[0].nosp[1]);
chmin(ans, dp[0].nosp[2]);
} else {
chmin(ans, dp[0].nosp[0] + w.back());
chmin(ans, dp[0].nosp[1] + w.back());
chmin(ans, dp[0].nosp[2] + w.back());
}
REP(wi, 2) REP(l, 3) REP(r, 3) {
if (is_ok(wi, r, l)) {
chmin(ans, dp[0].sp[wi][l][r]);
} else {
chmin(ans, dp[0].sp[wi][l][r] + w.back());
}
}
return ans;
}