#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#define N 100000
#define M 11
#define K 6
#define inf 1e18
using namespace std;
struct reads
{
    int num;
    long long data;
};
struct node
{
    int rt[K+1];
    bool operator < (const node &t)const
    {
        for (int i=1;i<=6;++i)
	    if (rt[i]!=t.rt[i])
		return rt[i]<t.rt[i];
	return 0;
    }
};
node st,tong[N+1];
map<node,int>p;
int n,leng,lengs,length,rt[N+1],nt[N+1],l[N+1],r[N+1],num[N+1];
long long dp[N+1][M+1],DP[M+1],delta[N+1];
vector<reads>E[N+1];
void add(int x,int y,long long z)
{
    E[x].push_back((reads){y,z});
    return;
}
int find(int x)
{
    if (rt[x]==x) return x;
    return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
    if (find(x)!=find(y))
    {
	if (find(x)<find(y)) swap(x,y);
	rt[find(x)]=find(y);
    }
    return;
}
int F(int x,int op)
{
    return ((x-1)<<1)+op+1;
}
bool check(node d)
{
    for (int i=1;i<=3;++i)
	if (rt[F(i,0)]==rt[F(i,1)])
	    return 0;
    return 1;
}
void dfs(int x)
{
    long long res;
    if (num[x])
    {
	for(int i=1;i<=6;++i) rt[i]=i;
	unionn(F(1,0),F(2,0)),unionn(F(1,0),F(3,0)),unionn(F(1,1),F(2,1)),unionn(F(1,1),F(3,1));
	for (int i=1;i<=6;++i) st.rt[i]=rt[i];
	dp[x][p[st]]=0,l[x]=r[x]=num[x];
    }
    else
    {
	for (int i=0;i<E[x].size();++i)
	{
	    dfs(E[x][i].num);
	    if (!i)
	    {
		for (int j=0;j<=1;++j)
		    for (int k=1;k<=11;++k)
			if (dp[E[x][i].num][k]!=inf)
			{
			    res=0;
			    for (int t=1;t<=8;++t) rt[t]=t;
			    if (tong[k].rt[F(1,0)]==tong[k].rt[F(2,0)]) unionn(F(4,0),F(2,0)),unionn(F(4,1),F(2,1));
			    if (tong[k].rt[F(1,0)]==tong[k].rt[F(3,0)]) unionn(F(4,0),F(3,0)),unionn(F(4,1),F(3,1));
			    if (tong[k].rt[F(2,0)]==tong[k].rt[F(3,0)]) unionn(F(2,0),F(3,0)),unionn(F(2,1),F(3,1));
			    if (tong[k].rt[F(1,0)]==tong[k].rt[F(2,1)]) unionn(F(4,0),F(2,1)),unionn(F(4,1),F(2,0));
			    if (tong[k].rt[F(1,0)]==tong[k].rt[F(3,1)]) unionn(F(4,0),F(3,1)),unionn(F(4,1),F(3,0));
			    if (tong[k].rt[F(2,0)]==tong[k].rt[F(3,1)]) unionn(F(2,0),F(3,1)),unionn(F(2,1),F(3,0));
			    if (!j) unionn(F(1,0),F(4,1)),unionn(F(1,1),F(4,0));
			    else res+=E[x][i].data;
			    for (int t=1;t<=6;++t) st.rt[t]=find(t);
			    if (check(st)) dp[x][p[st]]=min(dp[x][p[st]],dp[E[x][i].num][k]+res);
			}
		l[x]=l[E[x][i].num],r[x]=r[E[x][i].num];
	    }
	    else
	    {
		for (int j=1;j<=11;++j) DP[j]=inf;
		for (int j=0;j<=1;++j)
		    for (int k=0;k<=1;++k)
			for (int s=1;s<=11;++s)
			    if (dp[x][s]!=inf)
				for (int w=1;w<=11;++w)
				    if (dp[E[x][i].num][w]!=inf)
				    {
					res=0;
					for (int t=1;t<=12;++t) rt[t]=t;
					if (tong[s].rt[F(1,0)]==tong[s].rt[F(2,0)]) unionn(F(1,0),F(2,0)),unionn(F(1,1),F(2,1));
					if (tong[s].rt[F(1,0)]==tong[s].rt[F(3,0)]) unionn(F(1,0),F(4,0)),unionn(F(1,1),F(4,1));
					if (tong[s].rt[F(2,0)]==tong[s].rt[F(3,0)]) unionn(F(2,0),F(4,0)),unionn(F(2,1),F(4,1));
					if (tong[s].rt[F(1,0)]==tong[s].rt[F(2,1)]) unionn(F(1,0),F(2,1)),unionn(F(1,1),F(2,0));
					if (tong[s].rt[F(1,0)]==tong[s].rt[F(3,1)]) unionn(F(1,0),F(4,1)),unionn(F(1,1),F(4,0));
					if (tong[s].rt[F(2,0)]==tong[s].rt[F(3,1)]) unionn(F(2,0),F(4,1)),unionn(F(2,1),F(4,0));
					if (tong[w].rt[F(1,0)]==tong[w].rt[F(2,0)]) unionn(F(5,0),F(6,0)),unionn(F(5,1),F(6,1));
					if (tong[w].rt[F(1,0)]==tong[w].rt[F(3,0)]) unionn(F(5,0),F(3,0)),unionn(F(5,1),F(3,1));
					if (tong[w].rt[F(2,0)]==tong[w].rt[F(3,0)]) unionn(F(6,0),F(3,0)),unionn(F(6,1),F(3,1));
					if (tong[w].rt[F(1,0)]==tong[w].rt[F(2,1)]) unionn(F(5,0),F(6,1)),unionn(F(5,1),F(6,0));
					if (tong[w].rt[F(1,0)]==tong[w].rt[F(3,1)]) unionn(F(5,0),F(3,1)),unionn(F(5,1),F(3,0));
					if (tong[w].rt[F(2,0)]==tong[w].rt[F(3,1)]) unionn(F(6,0),F(3,1)),unionn(F(6,1),F(3,0));
					if (!j) unionn(F(1,0),F(5,1)),unionn(F(1,1),F(5,0));
					else res+=E[x][i].data;
					if (!k) unionn(F(4,0),F(6,1)),unionn(F(4,1),F(6,0));
					else res+=delta[r[x]];
					for (int t=1;t<=6;++t) st.rt[t]=find(t);
					if (check(st)) DP[p[st]]=min(DP[p[st]],dp[x][s]+dp[E[x][i].num][w]+res);
				    }
		for (int j=1;j<=11;++j) dp[x][j]=DP[j];
		r[x]=r[E[x][i].num];
	    }
	}
    }
    return;
}
long long place_police(vector<int>P,vector<long long>C,vector<long long>W)
{
    long long res,ans=inf;
    n=P.size()+1;
    for (int i=2;i<=n;++i) add(P[i-2]+1,i,C[i-2]);
    for (int i=1;i<=n;++i)
	if (E[i].empty())
	    num[i]=++leng,delta[leng]=W[leng-1];
    for (int i=0;i<(1<<6);++i)
    {
	for (int j=1;j<=6;++j) rt[j]=j;
	if (i&(1<<0)) unionn(F(1,0),F(2,0)),unionn(F(1,1),F(2,1));
	if (i&(1<<1)) unionn(F(1,0),F(3,0)),unionn(F(1,1),F(3,1));
	if (i&(1<<2)) unionn(F(2,0),F(3,0)),unionn(F(2,1),F(3,1));
	if (i&(1<<3)) unionn(F(1,0),F(2,1)),unionn(F(1,1),F(2,0));
	if (i&(1<<4)) unionn(F(1,0),F(3,1)),unionn(F(1,1),F(3,0));
	if (i&(1<<5)) unionn(F(2,0),F(3,1)),unionn(F(2,1),F(3,0));
	for (int j=1;j<=6;++j) st.rt[j]=find(j);
        if (check(st)&&p.find(st)==p.end()) tong[++lengs]=st,p[st]=lengs;
    }
    for (int i=1;i<=n;++i)
	for (int j=0;j<=11;++j)
	    dp[i][j]=inf;
    dfs(1);
    for (int i=0;i<=1;++i)
	for (int j=1;j<=11;++j)
	{
	    res=0;
	    for (int k=1;k<=6;++k) rt[k]=tong[j].rt[k];
	    if (!i) unionn(F(2,0),F(3,1)),unionn(F(2,1),F(3,0));
	    else res+=delta[leng];
	    for (int k=1;k<=6;++k) st.rt[k]=k;
	    if (check(st)) ans=min(ans,dp[1][j]+res);
	}
    return ans;
}

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