#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
inline int connects_self(int p) {
return p == 0 || p == 2;
}
inline int connects_neighbors(int p) {
return p == 1 || p == 2;
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
vector<vector<int>> children(n, vector<int>());
for (int i = 1; i < n; ++i) children[host[i]].push_back(i);
// first y/n: does there exist an indirect neighbor we picked
// (path of neighbor-connects that goes up, then a direct connect,
// then the path goes back down through neighbor-connects)
// second y/n: did we pick this node?
// note that yy cannot happen; since the indirect neighbor and this node
// are adjacent
vector<int> best_nn(n), best_yn(n), best_ny(n);
for (int i = n - 1; i >= 0; --i) {
// We do some DP to account for the fact that a child might become
// an indirect neighbor of another child's sibling.
// maintain DP on suffixes of the list of children:
// - max if we pick no neighbor-connected child
// - MUST pick yn if current child is neighbor-connected
// - max if we picked some neighbor-connected child
// - MUST pick yn if current child is self-connected but not neighbor-contained
// then transition to next on some table
// - otherwise, can pick any (?)
//
// Aside from this, the 3 cases are:
// best_nn: this DP runs as normal
// best_yn: MUST pick yn if child connects_neighbors
// best_ny: MUST pick yn if child connects_self
//
// (these conditions being active are denoted by free_neighbor and free_self = false,
// respectively)
for (auto recurrence : {0, 1, 2}) { // nn, yn, ny
vector<int> &table = (recurrence == 0 ? best_nn :
(recurrence == 1 ? best_yn : best_ny));
vector<int> no_neigh_connect(children.size() + 1), with_neigh_connect(children.size() + 1);
bool free_neighbor = recurrence != 1;
bool free_self = recurrence != 2;
for (int k = (int)children[i].size() - 1; k >= 0; --k) {
int v = children[i][k];
auto must_yn = [&] (int v, bool free_neighbor, bool free_self) {
bool must_yn = (!free_neighbor && connects_neighbors(protocol[v]))
|| (!free_self && connects_self(protocol[v]));
// cerr << "must yn " << must_yn << endl;
return must_yn;
};
// update no_neigh_connect[k]
if (must_yn(v, false, free_self)) {
no_neigh_connect[k] = best_yn[v] + no_neigh_connect[k+1];
} else {
no_neigh_connect[k] = best_nn[v] + no_neigh_connect[k+1];
if (!connects_neighbors(protocol[v])) {
no_neigh_connect[k] = max(no_neigh_connect[k], best_ny[v] + no_neigh_connect[k+1]);
}
}
// update with_neigh_connect[k]
if (must_yn(v, free_neighbor, free_self) || (connects_self(protocol[v]) && !connects_neighbors(protocol[v]))) {
with_neigh_connect[k] = best_yn[v] + with_neigh_connect[k+1];
} else {
with_neigh_connect[k] = best_nn[v] + with_neigh_connect[k+1];
with_neigh_connect[k] = max(with_neigh_connect[k], best_ny[v] + with_neigh_connect[k+1]);
if (connects_neighbors(protocol[v])) {
with_neigh_connect[k] = max(with_neigh_connect[k], best_ny[v] + no_neigh_connect[k+1]);
}
}
// cerr << "HN" << no_neigh_connect[k] << " " << with_neigh_connect[k] << endl;
}
if (children[i].size() > 0) {
table[i] = max(no_neigh_connect[0], with_neigh_connect[0]);
// cerr << "recc " << i << " " << recurrence << " " << table[i] << endl;
}
}
best_ny[i] += confidence[i];
// cerr << i << " values " << best_nn[i] << " " << best_yn[i] << " " << best_ny[i] << endl;
}
return max(best_nn[0], best_ny[0]);
}
