#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
void chmin(ll& a, ll b) { if(a > b) a = b; }

/*
 奇数サイクルではなくただのサイクルだったら, これは最大全域木
 マトロイドの構造を持っていないか？
 [マトロイドの構造] 木の部分を 2 色に塗り分けて, 両端が同色の辺の数を K とすると, K 本未満の削除では達成できず, K 本より多い削除は無駄な削除が含まれている
 → そんなことない
 外周の辺のどれを切るかを固定すると, … 外周のつながっている部分は 2 色交互になっていて, それを DP で繋げる
 DP じゃん なるほどね〜
 [部分木][部分木の根の色][部分木の葉の一番左の色][部分木の葉の一番右の色] := 部分木内のコストの最小値 で DP できる
 O(N)
 */
ll place_police(vector<int> P, vector<ll> C, vector<ll> W) {
    P.insert(P.begin(), -1);
    C.insert(C.begin(), -1);
    const ll N = P.size();
    vector childs(N, vector<ll>{});
    for(ll i = 1; i < N; i++) childs[P[i]].push_back(i);
    vector<ll> R(N);
    {
        ll K = 0;
        for(ll i = 0; i < N; i++) if(childs[i].empty()) R[i] = K++;
    }
    vector dp(N, array{INF, INF, INF, INF, INF, INF, INF, INF});
    for(ll i = N; --i; ) {
        if(childs[i].empty()) {
            dp[i][0] = dp[i][7] = 0;
        }
        const ll p = P[i];
        for(ll j = 0; j < 4; j++) {
            chmin(dp[i][j + 4], dp[i][j] + C[i]);
            chmin(dp[i][j], dp[i][j + 4] + C[i]);
            swap(dp[i][j], dp[i][j + 4]);
        }
        if(childs[p].back() == i) {
            dp[p] = dp[i];
            R[p] = R[i];
        }
        else {
            auto& dp1 = dp[i], & dp2 = dp[p];
            const ll w = W[R[i]];
            array dp3{INF, INF, INF, INF, INF, INF, INF, INF};
            for(ll j : {0, 4}) for(ll k : {0, 1, 2, 3}) for(ll l : {0, 1, 2, 3}) {
                chmin(dp3[j | k & 2 | l & 1], dp1[j | k] + dp2[j | l] + ((k & 1) == (l >> 1) ? w : 0));
            }
            dp2 = dp3;
        }
    }
    ll ans = INF;
    auto& dp1 = dp[0];
    for(ll k : {0, 1, 2, 3}) chmin(ans, dp1[k] + ((k >> 1) == (k & 1) ? W.back() : 0));
    return ans;
}

cc1plus: fatal error: implementer.cpp: No such file or directory
compilation terminated.