#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];
}
}
// Find out best sample
int findSample(int n, int confidence[], int host[], int 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]);
/*
vvi dp(n, vi(2, 0));
dp[0][0] = confidence[0]; // best res with zero
dp[0][1] = 0; // best rest without 0
ll bestRes = confidence[0];
for (int t = 1; t < n; ++t)
{
}
return sum;
*/
}
