#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int NMAX = 100000;
int n;
int a[NMAX + 5], hosst[NMAX + 5], p[NMAX + 5];
set<int> fl[3 * NMAX + 5], fr[3 * NMAX + 5];
int t[3 * NMAX + 5];
int tip[3 * NMAX + 5], cr;///pentru cei > n, 1 -> normal, 2 -> sus
set<int> roots;
bool idk[NMAX + 5];
int dp[3 * NMAX + 5], dp2[3 * NMAX + 5];
void dfs(int nod)
{
if (nod <= n)
dp[nod] = a[nod], dp2[nod] = 0;
else
{
for (auto fiu : fl[nod])
dfs(fiu);
for (auto fiu : fr[nod])
dfs(fiu);
dp[nod] = dp2[nod] = 0;
if (tip[nod] == 1)
{
for (auto fiu : fl[nod])
dp2[nod] += dp2[fiu];
for (auto fiu : fr[nod])
dp2[nod] += dp2[fiu];
int crr;
crr = 0;
for (auto fiu : fl[nod])
crr += dp[fiu];
for (auto fiu : fr[nod])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
crr = 0;
for (auto fiu : fr[nod])
crr += dp[fiu];
for (auto fiu : fl[nod])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
}
else
{
for (auto fiu : fl[nod])
dp2[nod] += dp2[fiu];
for (auto fiu : fr[nod])
dp2[nod] += dp[fiu];
int crr;
crr = 0;
for (auto fiu : fl[nod])
crr += dp[fiu];
for (auto fiu : fr[nod])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
crr = 0;
for (auto fiu : fr[nod])
crr += dp[fiu];
for (auto fiu : fl[nod])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
}
}
}
int solve(int root)
{
dfs(root);
return dp[root];
}
int findSample(int N, int Confidence[], int Host[], int Protocol[])
{
n = N;
for (int i = 1; i <= n; i++)
a[i] = Confidence[i - 1];
for (int i = 2; i <= n; i++)
hosst[i] = Host[i - 1] + 1;
for (int i = 2; i <= n; i++)
p[i] = Protocol[i - 1];
cr = n;
roots.insert(1);
for (int i = 2; i <= n; i++)
{
if (!idk[hosst[i]] and p[i] == 1)
roots.insert(i);
else
{
idk[i] = true;
if (!idk[hosst[i]])
{
idk[hosst[i]] = true;
cr++;
tip[cr] = 1;
roots.erase(hosst[i]);
roots.insert(cr);
fl[cr].insert(hosst[i]);
fr[cr].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
if (p[i] == 1)
{
int cn = t[hosst[i]];
t[i] = cn;
if (fl[cn].find(hosst[i]) != fl[cn].end())
fl[cn].insert(i);
else
fr[cn].insert(i);
}
else if (p[i] == 0)
{
int cn = t[hosst[i]];
cr++;
tip[cr] = 2;
t[cr] = cn;
bool inst = false;
if (fl[cn].find(hosst[i]) != fl[cn].end())
inst = true;
if (inst)
{
fl[cn].erase(hosst[i]);
fl[cn].insert(cr);
fl[cr].insert(hosst[i]);
fr[cr].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
fr[cn].erase(hosst[i]);
fr[cn].insert(cr);
fl[cr].insert(hosst[i]);
fr[cr].insert(i);
t[i] = t[hosst[i]] = cr;
}
}
else if (p[i] == 2)
{
int cn = t[hosst[i]];
cr++;
tip[cr] = 1;
bool inst = false;
if (fl[cn].find(hosst[i]) != fl[cn].end())
inst = true;
if (inst)
{
fl[cn].erase(hosst[i]);
fl[cn].insert(cr);
fl[cr].insert(hosst[i]);
fr[cr].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
fr[cn].erase(hosst[i]);
fr[cn].insert(cr);
fl[cr].insert(hosst[i]);
fr[cr].insert(i);
t[i] = t[hosst[i]] = cr;
}
}
}
}
}
/*for (int i = n + 1; i <= cr; i++)
{
cout << i << ' ' << tip[i] << endl;
for (auto it : fl[i])
cout << it << ' ';
cout << endl;
for (auto it : fr[i])
cout << it << ' ';
cout << endl;
cout << endl;
}*/
int ans = 0;
for (auto it : roots)
ans += solve(it);
return ans;
}
/*
6
13 3 6 20 10 15
0 0
0 1
1 2
2 1
0 0
*/
