#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5 + 5;
const ll linf = 0x3f3f3f3f3f3f3f3f;

void chk_min(ll &a,ll b){ if(a>b) a=b;}

int encode(int l,int r,int mid){ return l * 9 + r * 3 + mid;}
void decode(int mask,int &l,int &r,int &mid){ l = mask / 9; r = mask / 3 % 3; mid = mask % 3;}

int flip(int x){ return x == 2? 2: x ^ 1;}
int encode(bool *a){ return a[0]? 0: a[1]? 1: 2;}

int trans1[27][2];
vector< array<int,3> > trans2;

vector< pair<int,ll> > g[MAXN];
ll c[MAXN];

using Data = array<ll,27>;

Data update(Data dp,ll w)
{
	Data res; res.fill(linf);
	for(int mask=0; mask<27; ++mask)
	{
		if(dp[mask] == linf) continue;
		chk_min(res[trans1[mask][0]], dp[mask] + w);
		chk_min(res[trans1[mask][1]], dp[mask]);
	}
	return res;
}

Data operator + (Data A,Data B)
{
	Data res; res.fill(linf);
	for(auto t: trans2)
		chk_min(res[t[2]], A[t[0]] + B[t[1]]);
	return res;
}

Data dp[MAXN];
void dfs_dp(int u)
{
	dp[u].fill(linf);
	
	if(!g[u].size())
	{
		dp[u][encode(0,1,1)] = 0;
		dp[u][encode(0,2,2)] = c[u];
		return;
	}
	
	bool flag = 0;
	for(auto t: g[u])
	{
		int v = t.first; ll w = t.second;
		dfs_dp(v);
		if(flag)
			dp[u] = dp[u] + update(dp[v], w);
		else
			dp[u] = update(dp[v], w), flag = 1;
	}
}

ll place_police(vector<int> _anc, vector<ll> _c, vector<ll> _w)
{
	for(int mask1=0; mask1<27; ++mask1)
	{
		int l1, r1, mid1; decode(mask1, l1, r1, mid1);
		trans1[mask1][0] = encode(2, 2, mid1);
		trans1[mask1][1] = encode(flip(l1), flip(r1), mid1);
	}
	for(int mask1=0; mask1<27; ++mask1)
		for(int mask2=0; mask2<27; ++mask2)
		{
			static bool has[4][4][2];
			memset(has, 0, sizeof(has));
			
			auto upd = [&] (int mask,int u,int v1,int v2)
			{
				int l, r, mid;
				decode(mask, l, r, mid);
				if(l != 2) has[u][v1][l] = has[v1][u][l] = 1;
				if(r != 2) has[u][v2][r] = has[v2][u][r] = 1;
				if(mid != 2) has[v1][v2][mid] = has[v2][v1][mid] = 1;
			};
			
			upd(mask1, 0, 1, 3);
			upd(mask2, 0, 3, 2);
			
			for(int i=0; i<4; ++i)
				has[i][i][0] = 1;
			
			for(int k=0; k<4; ++k)
				for(int i=0; i<4; ++i) for(int x=0; x<=1; ++x) if(has[i][k][x])
				for(int j=0; j<4; ++j) for(int y=0; y<=1; ++y) if(has[k][j][y])
					has[i][j][x ^ y] = 1;
			
			bool valid = 1;
			for(int i=0; i<4; ++i)
				valid &= has[i][i][1] == 0;
			
			if(valid)
			{
				int l = encode(has[0][1]);
				int r = encode(has[0][2]);
				int mid = encode(has[1][2]);
				trans2.push_back({mask1, mask2, encode(l, r, mid)});
			}
		}
	
	int n = (int)_anc.size() + 1;
	for(int i=2; i<=n; ++i)
	{
		int j = _anc[i-2] + 1;
		g[j].emplace_back(i, _c[i-2]);
	}
	
	vector<int> leaf;
	for(int i=1; i<=n; ++i)
		if(!g[i].size())
			leaf.emplace_back(i);
	
	for(int i=0; i<(int)leaf.size(); ++i)
		c[leaf[i]] = _w[i];
	
	dfs_dp(1);
	
	ll ans = linf;
	for(int mask=0; mask<27; ++mask)
	{
		int l,r,mid; decode(mask, l, r, mid);
		if(mid == 1) continue;
		chk_min(ans, dp[1][mask]);
	}
	return ans;
}

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