#include <bits/stdc++.h>
using namespace std;
int matrix[11][11];
int subTrees[2000][2];
int degrees[2000];
vector<int> graph[2000];
vector<int> confs;
int globMax = 0;
int n;
int tryItOut(vector<int> v) {
for (int i = 0; i < v.size(); i++)
{
for (int j = i+1; j < v.size(); j++)
{
if (matrix[v[i]][v[j]])
{
return 0;
}
}
}
int toRet = 0;
for (int i = 0; i < v.size(); i++)
{
toRet += confs[v[i]];
}
return toRet;
}
void doStuff(int x, vector<int> v) {
if (x == n) {
globMax = max(globMax, tryItOut(v));
return;
}
v.push_back(x);
doStuff(x+1, v);
v.pop_back();
doStuff(x+1, v);
}
int sub1(int n, int confidence[], int host[], int protocol[]) {
for (int i = 1; i < n; i++)
{
if (protocol[i] == 0)
{
matrix[i][host[i]] = 1;
matrix[host[i]][i] = 1;
}
else if (protocol[i] == 1)
{
for (int j = 0; j < 11; j++)
{
if (matrix[host[i]][j] == 1)
{
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}
}
else
{
for (int j = 0; j < 11; j++)
{
if (matrix[host[i]][j] == 1)
{
matrix[i][j] = 1;
matrix[j][i] = 1;
}
}
matrix[i][host[i]] = 1;
matrix[host[i]][i] = 1;
}
}
vector<int> v;
doStuff(0, v);
return globMax;
}
int maxSubtree(int node, bool canInclude) {
if (subTrees[node][canInclude] > 0)
{
return subTrees[node][canInclude];
}
if (graph[node].size() == 0)
{
if (canInclude)
{
return confs[node];
}
return 0;
}
if (!canInclude)
{
int totSum = 0;
for (auto i : graph[node])
{
totSum += maxSubtree(i, true);
}
subTrees[node][canInclude] = totSum;
return totSum;
}
int totSum1 = 0;
for (auto i : graph[node])
{
totSum1 += maxSubtree(i, true);
}
int totSum2 = confs[node];
for (auto i : graph[node])
{
totSum2 += maxSubtree(i, false);
}
int totSum = max(totSum1, totSum2);
subTrees[node][canInclude] = totSum;
return totSum;
}
int sub5(int N, int confidence[], int host[], int protocol[]) {
int totDegree = 0;
for (int i = 1; i < N; i++)
{
if (protocol[i] == 0)
{
degrees[i] = 1;
degrees[host[i]]++;
graph[i].push_back(host[i]);
graph[host[i]].push_back(i);
totDegree += 2;
}
if (protocol[i] == 1)
{
degrees[i] = degrees[host[i]];
totDegree += 2 * degrees[host[i]];
for (auto j : graph[host[i]])
{
degrees[j]++;
graph[j].push_back(i);
graph[i].push_back(j);
}
}
}
int toRet = N;
while (totDegree > 0)
{
int maxDegree = 0;
int maxIndex = -1;
for (int i = 0; i < N; i++)
{
if (degrees[i] >= maxDegree)
{
maxDegree = degrees[i];
maxIndex = i;
}
}
toRet--;
//cout << "Removing " << maxIndex << "\n";
totDegree -= maxDegree;
degrees[maxIndex] = 0;
for (auto i : graph[maxIndex])
{
if (degrees[i] > 0)
{
degrees[i]--;
totDegree--;
}
}
graph[maxIndex].clear();
}
return toRet;
}
int findSample(int N, int confidence[], int host[], int protocol[]) {
n = N;
int confSum = 0;
int confMax = 0;
for (int i = 0; i < n; i++)
{
confs.push_back(confidence[i]);
confSum += confs[i];
confMax = max(confMax, confs[i]);
}
if (confMax == 1)
{
return sub5(n, confidence, host, protocol);
}
if (n <= 10)
{
n = N;
return sub1(n, confidence, host, protocol);
}
if (protocol[1] == 1)
{
return confSum;
}
if (protocol[1] == 2)
{
return confMax;
}
for (int i = 1; i < n; i++)
{
graph[host[i]].push_back(i);
//graph[i].push_back(host[i]);
}
return maxSubtree(0, true);
}
