#include "friend.h"
#include "bits/stdc++.h"
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
void dfs(int v, int p, vvi &adj, vvi &mxt, const int C[])
{
mxt[v][1] = C[v];
for (int u : adj[v])
{
if (u == p)
continue;
dfs(u, v, adj, mxt, C);
mxt[v][0] += max(mxt[u][0], mxt[u][1]);
mxt[v][1] += mxt[u][0];
}
}
// subtask bruteforce
int bruteforce(int n, int confidence[], int host[], int protocol[])
{
vi forbidden;
vvi adj(n);
for (int t = 1; t < n; ++t)
{
int h = host[t];
if (protocol[t] == 1 || protocol[t] == 2) // My & We
for (int u : adj[h])
{
adj[u].push_back(t), adj[t].push_back(u);
assert(u != t);
forbidden.push_back((1 << u) + (1 << t));
}
if (protocol[t] == 0 || protocol[t] == 2) // I & We
{
adj[h].push_back(t), adj[t].push_back(h);
assert(t != h);
forbidden.push_back((1 << h) + (1 << t));
}
}
int maxres = 0;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask)
{
bool bad = false;
for (int f : forbidden)
if ((f & bitmask) == f)
{
bad = true;
break;
}
if (bad)
continue;
int res = 0;
for (int i = 0; i < n; ++i)
if (bitmask & (1 << i))
res += confidence[i];
maxres = max(res, maxres);
}
return maxres;
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int protocol[])
{
// if (n <= 10)
// return bruteforce(n, confidence, host, protocol);
vi C(n);
// copy(confidence, confidence + n, C.begin());
// subtaks 2: only my friends are your friends -> independent set!
// int sum = accumulate(confidence, confidence + n, 0);
// subtask 3: only we are your friends -> complete graph
// int maxi = *max_element(confidence, confidence + n);
// subtask 4: only I am your friend -> tree dp
/*
vvi adj(n);
for (int t = 1; t < n; ++t)
{
adj[host[t]].push_back(t);
adj[t].push_back(host[t]);
}
vvi max_subtree(n, vi(2, 0)); // max subtree without and with corresponding root
dfs(0, 0, adj, max_subtree, confidence);
return max(max_subtree[0][0], max_subtree[0][1]);
*/
int ans = 0;
for (int t = n - 1; t > 0; --t)
{
if (protocol[t] == 0)
{
// I
confidence[host[t]] = max(0, confidence[host[t]] - confidence[t]);
ans += confidence[t];
}
else if (protocol[t] == 1)
{
// My
confidence[host[t]] += confidence[t];
}
else
{
// We
}
}
ans += confidence[0];
return ans;
}
