#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;
}
int sub4(int n, int confidence[], int host[], int protocol[])
{
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 find_augmenting_path(vvi &adj, int v, vi &matching)
{
for (int u : adj[v])
{
if (matching[u] == v)
continue;
if (matching[u] == -1 || find_augmenting_path(adj, matching[u], matching))
{
matching[u] = v;
matching[v] = u;
return 1;
}
}
return 0;
}
int sub5(int n, int confidence[], int host[], int protocol[])
{
vvi adj(n);
vi side(n);
side[0] = 0;
for (int t = 1; t < n; ++t)
{
int h = host[t];
if (protocol[t] == 1) // My
{
for (int u : adj[h])
adj[u].push_back(t), adj[t].push_back(u);
side[t] = side[h];
}
if (protocol[t] == 0) // I
{
adj[h].push_back(t), adj[t].push_back(h);
side[t] = 1 - side[h];
}
}
vi matching(n, -1);
for (int i = 0; i < n; ++i)
{
int should_break = true;
for (int u = 0; u < n; ++u)
{
if (side[u] == 0 && matching[u] == -1)
should_break |= find_augmenting_path(adj, u, matching);
}
if (should_break)
break;
}
vi vis(n, 0);
stack<int> st;
for (int i = 0; i < n; ++i)
if (side[i] == 0 && matching[i] == -1)
st.push(i), vis[i] = 1;
while (!st.empty())
{
int v = st.top();
st.pop();
for (int u : adj[v])
{
assert(matching[u] != -1);
vis[u] = 1;
if (vis[matching[u]] == 0)
st.push(matching[u]), vis[matching[u]] = 1;
}
}
int ans = n;
for (int i = 0; i < n; ++i)
{
if (side[i] == 0)
{
if (vis[i] == 0)
--ans;
}
else
{
if (vis[i] == 1)
--ans;
}
}
return ans;
}
// 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
// return sub4(n, confidence, host, protocol);
// subtask 5: I and My -> G is bipartite -> size of max independent set
return sub5(n, confidence, host, protocol);
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
confidence[host[t]] = max(confidence[host[t]], confidence[t]);
}
}
ans += confidence[0];
return ans;
}
