#include <iostream>
#include <stdio.h>
#include <vector>
#include "friend.h"
//#include "grader.cpp"
using namespace std;
const long long mxn = 3e5 + 10;
vector <int> pa[mxn] = {},chi[mxn] = {};
int nn,econ[mxn] = {},ma = 0,chv[mxn] = {},sev[mxn] = {},gr[mxn] = {},ru,cw[mxn] = {},rep[mxn] = {},sta[mxn] = {};
long long fima(long long l,long long r)
{
if(l > r)
return l;
return r;
}
//gli[mxn] = {},u[mxn] = {},ra[mxn] = {},
//long long figr(long long l)
//{
// long long cn = l,f;
// while(gr[cn] != cn)
// {
// cn = gr[cn];
// }
// while(gr[l] != l)
// {
// f = gr[l];
// gr[l] = cn;
// l = f;
// }
// return cn;
//}
//long long mer(long long l,long long r)
//{
// long long pl,pr;
// pl = figr(l);
// pr = figr(r);
//}
//long long re(long long la,long long su)
//{
// long long fn,i,j,cu[mxn] = {};
// ma = fima(su,ma);
// for(i=0; i<nn; i++)
// {
// cu[i] = u[i];
// }
// for(i=0; i<nn; i++)
// {
// if(cu[i] == 0)
// {
// for(j=0; j<pa[i].size(); j++)
// {
// u[pa[i][j]] = 1;
// }
// u[i] = 1;
// re(la+1,su + econ[i]);
// for(j=0; j<nn; j++)
// {
// u[j] = cu[j];
// }
// }
// }
// return 0;
//}
//long long re2(long long cn,long long be);
long long rech(long long cn,long long hon);
long long re3(long long cn)
{
long long i,fn;
for(i=0; i<pa[cn].size(); i++)
{
fn = pa[cn][i];
rech(fn,1);
sev[cn] += chv[fn];
chv[cn] += sev[fn];
}
// if(sev[cn] < chv[cn])
// {
// sev[cn] = chv[cn];
// }
return 0;
}
long long rech(long long cn,long long hon)
{
long long i,fn,cva,cma;
if(chi[cn].size() == 0)
{
sev[cn] = econ[rep[cn]];
re3(cn);
if(sev[cn] < chv[cn])
{
sev[cn] = chv[cn];
}
return 0;
}
re3(cn);
if(sta[cn] == 1)
{
for(i=0; i<chi[cn].size(); i++)
{
fn = chi[cn][i];
rech(fn,0);
// if(sta[cn] == 1)
// {
sev[cn] += sev[fn];
chv[cn] += chv[fn];
// }
// else
// {
// sev[cn] += fima(sev[fn] + )
// }
}
}
else
{
cva = 0;
cma = -1;
for(i=0; i<chi[cn].size(); i++)
{
fn = chi[cn][i];
rech(fn,0);
cva += chv[fn];
}
chv[cn] += cva;
for(i=0; i<chi[cn].size(); i++)
{
fn = chi[cn][i];
cma = fima(cma,cva - chv[fn] + sev[fn]);
}
sev[cn] += cma;
}
if(sev[cn] < chv[cn])
{
sev[cn] = chv[cn];
}
// if(sev[cn] < chv[cn] && hon == 1)
// {
// sev[cn] = chv[cn];
// }
return 0;
}
//long long re2(long long cn,long long be)
//{
// long long i,fn;
// if(cn < nn)
// sev[cn] = econ[cn];
// for(i=0; i<pa[cn].size(); i++)
// {
// fn = pa[cn][i];
// if(fn == be)
// {
// continue;
// }
// re2(fn,cn);
// sev[cn] += chv[fn];
// chv[cn] += sev[fn];
// }
// if(chv[cn] > sev[cn])
// {
// sev[cn] = chv[cn];
// }
// return 0;
//}
int findSample(int n,int conf[],int ho[],int prot[])
{
long long i,j,ans,cn,fn;
nn = n;
ru = n;
for(i=0; i<n; i++)
{
econ[i] = conf[i];
gr[i] = i;
cw[i] = i;
rep[i] = i;
// ma = fima(ma,conf[i]);
}
for(i=1; i<n; i++)
{
// ho[i] = gr[ho[i]];
if(prot[i] == 0)
{
pa[cw[ho[i]]].push_back(i);
// pa[i].push_back(cw[ho[i]]);
}
else if(prot[i] == 1)
{
// cn = ho[i];
gr[i] = gr[ho[i]];
chi[cw[ho[i]]].push_back(i);
chi[cw[ho[i]]].push_back(ru);
sta[cw[ho[i]]] = 1;
rep[ru] = ho[i];
cw[ho[i]] = ru;
ru ++;
// econ[cn] += econ[i];
// gr[i] = ho[i];
// for(j=0; j<pa[cn].size(); j++)
// {
// fn = pa[cn][j];
// pa[i].push_back(fn);
// pa[fn].push_back(i);
// }
}
else
{
gr[i] = gr[ho[i]];
chi[cw[ho[i]]].push_back(i);
chi[cw[ho[i]]].push_back(ru);
sta[cw[ho[i]]] = 2;
rep[ru] = ho[i];
cw[ho[i]] = ru;
ru ++;
// cn = ho[i];
// econ[cn] = fima(econ[cn],econ[i]);
// gr[i] = ho[i];
// for(j=0; j<pa[cn].size(); j++)
// {
// fn = pa[cn][j];
// pa[i].push_back(fn);
// pa[fn].push_back(i);
// }
// pa[cn].push_back(i);
// pa[i].push_back(cn);
}
}
rech(0,1);
ma = fima(sev[0],chv[0]);
// re(0,0);
return ma;
}
//int main()
//{
// cout << "Hello world!" << endl;
// return 0;
//}
