#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[NMAX + 5], fr[NMAX + 5];
int t[2 * NMAX + 5];
int tip[2 * NMAX + 5], cr;///pentru cei > n, 1 -> normal, 2 -> sus
bool isroot[2 * NMAX + 5];
bool idk[NMAX + 5];
int dp[2 * NMAX + 5], dp2[2 * NMAX + 5];
void dfs(int nod)
{
if (nod <= n)
dp[nod] = a[nod], dp2[nod] = 0;
else
{
for (auto fiu : fl[nod - n])
dfs(fiu);
for (auto fiu : fr[nod - n])
dfs(fiu);
dp[nod] = dp2[nod] = 0;
if (tip[nod] == 1)
{
for (auto fiu : fl[nod - n])
dp2[nod] += dp2[fiu];
for (auto fiu : fr[nod - n])
dp2[nod] += dp2[fiu];
int crr;
crr = 0;
for (auto fiu : fl[nod - n])
crr += dp[fiu];
for (auto fiu : fr[nod - n])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
crr = 0;
for (auto fiu : fr[nod - n])
crr += dp[fiu];
for (auto fiu : fl[nod - n])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
}
else
{
for (auto fiu : fl[nod - n])
dp2[nod] += dp2[fiu];
for (auto fiu : fr[nod - n])
dp2[nod] += dp[fiu];
int crr;
crr = 0;
for (auto fiu : fl[nod - n])
crr += dp[fiu];
for (auto fiu : fr[nod - n])
crr += dp2[fiu];
dp[nod] = max(dp[nod], crr);
crr = 0;
for (auto fiu : fr[nod - n])
crr += dp[fiu];
for (auto fiu : fl[nod - n])
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;
isroot[1] = true;
for (int i = 2; i <= n; i++)
{
if (!idk[hosst[i]] and p[i] == 1)
isroot[i] = true;
else
{
idk[i] = true;
if (!idk[hosst[i]])
{
idk[hosst[i]] = true;
cr++;
tip[cr] = 1;
isroot[hosst[i]] = false;
isroot[cr] = true;
fl[cr - n].insert(hosst[i]);
fr[cr - n].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
if (p[i] == 1)
{
int cn = t[hosst[i]];
t[i] = cn;
if (fl[cn - n].find(hosst[i]) != fl[cn - n].end())
fl[cn - n].insert(i);
else
fr[cn - n].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 - n].find(hosst[i]) != fl[cn - n].end())
inst = true;
if (inst)
{
fl[cn - n].erase(hosst[i]);
fl[cn - n].insert(cr);
fl[cr - n].insert(hosst[i]);
fr[cr - n].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
fr[cn - n].erase(hosst[i]);
fr[cn - n].insert(cr);
fl[cr - n].insert(hosst[i]);
fr[cr - n].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 - n].find(hosst[i]) != fl[cn - n].end())
inst = true;
if (inst)
{
fl[cn - n].erase(hosst[i]);
fl[cn - n].insert(cr);
fl[cr - n].insert(hosst[i]);
fr[cr - n].insert(i);
t[i] = t[hosst[i]] = cr;
}
else
{
fr[cn - n].erase(hosst[i]);
fr[cn - n].insert(cr);
fl[cr - n].insert(hosst[i]);
fr[cr - n].insert(i);
t[i] = t[hosst[i]] = cr;
}
}
}
}
}
int ans = 0;
for (int it = 1; it <= cr; it++)
if (isroot[it])
ans += solve(it);
return ans;
}
