#include "friend.h"
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> v2i;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
typedef vector<vb> v2b;
#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
vpi connections;
v2b adj;
v2i adj2;
vi bestincl;
vi bestexcl;
vi conf;
void connect(int a, int b) {
//cout << "Connected " << a << " and " << b << "\n";
if (a > b) swap(a, b);
connections.pb({ a, b });
adj[a][b] = true;
adj[b][a] = true;
adj2[a].pb(b);
adj2[b].pb(a);
}
int findbestexcl(int u, int p);
int findbestincl(int u, int p=-2) {
if (bestincl[u] != -1) return bestincl[u];
else {
int res = conf[u];
for (auto v : adj2[u]) {
if (v != p) {
res += findbestexcl(v, u);
}
}
bestincl[u] = res;
return res;
}
}
int findbestexcl(int u, int p = -2) {
if (bestexcl[u] != -1) return bestexcl[u];
else {
int res = 0;
for (auto v : adj2[u]) {
if (v != p) {
res += max(findbestincl(v, u), findbestexcl(v, u));
}
}
bestexcl[u] = res;
return res;
}
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
bool sub1 = false;
bool sub2 = true;
bool sub3 = true;
bool sub4 = true;
adj.resize(n, vb(n));
adj2.resize(n);
if (n <= 10) {
sub1 = true;
}
conf.pb(confidence[0]);
rept(i, 1, n) {
conf.pb(confidence[i]);
int h = host[i];
int prot = protocol[i];
if (prot == 0) {
sub3 = false;
sub2 = false;
connect(h, i);
}
else if (prot == 1) {
sub3 = false;
sub4 = false;
rep(j, i) {
if (j != h && adj[j][h]) {
connect(j, i);
}
}
}
else {
sub4 = false;
sub2 = false;
rep(j, i) {
if (adj[j][h] || j == h) {
connect(j, i);
}
else {
//cout << "Didn't connect " << j << " and " << i << "\n";
}
}
}
}
//------------debug------------
//sub1 = false, sub2 = false, sub3 = false;
//-----------------------------
if (sub1) {
vi sub(n);
int maxc = 0;
int totc = 0;
rep(i, (1 << n) - 1) {
//generate next subset
int j = n-1;
totc += confidence[j];
while (++sub[j] > 1) {
sub[j--] = 0;
totc += confidence[j] - 2 * confidence[j+1];
}
// check if the subset is valid
if (totc > maxc) {
bool valid = true;
for (int j = 0; j < connections.size() && valid; j++)
{
valid = !(sub[connections[j].first] && sub[connections[j].second]);
}
if (valid) {
maxc = totc;
}
}
}
return maxc;
}
if (sub2) {
int totc = 0;
rep(i, n) {
totc += confidence[i];
}
return totc;
}
if (sub3) {
int maxc = 0;
rep(i, n) {
maxc = max(maxc, confidence[i]);
}
return maxc;
}
if (sub4) {
bestincl.resize(n, -1);
bestexcl.resize(n, -1);
return max(findbestincl(0), findbestexcl(0));
}
}
