#include "friend.h"
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iostream>
using namespace std;
const int maxn=1005;
int n;
vector < int > ms[maxn];
int naj;
bool idem[15];
int val[maxn];
void probaj(){
int sol=0;
for(int i=0; i<n; i++){
if(idem[i]){
sol+=val[i];
for(int j=0; j<(int)ms[i].size(); j++){
if(idem[ms[i][j]]){
return;
}
}
}
}
naj=max(naj, sol);
}
void rek(int x){
if(x==n){
probaj();
return;
}
idem[x]=1;
rek(x+1);
idem[x]=0;
rek(x+1);
}
int dp[maxn][2];
void dfs(int x, int prosl){
dp[x][1]=val[x];
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]!=prosl){
dfs(ms[x][i], x);
dp[x][0]+=max(dp[ms[x][i]][0], dp[ms[x][i]][1]);
dp[x][1]+=dp[ms[x][i]][0];
}
}
}
int findSample(int a, int l[], int parent[], int koji[]){
n=a;
for(int i=0; i<n; i++){
val[i]=l[i];
}
int ok=0;
if(n<=1000){
for(int i=1; i<n; i++){
if(koji[i]==0){
ok|=1;
ms[parent[i]].push_back(i);
ms[i].push_back(parent[i]);
}
else if(koji[i]==1){
ok|=2;
for(int j=0; j<(int)ms[parent[i]].size(); j++){
ms[ms[parent[i]][j]].push_back(i);
ms[i].push_back(ms[parent[i]][j]);
}
}
else{
ok|=4;
for(int j=0; j<(int)ms[parent[i]].size(); j++){
ms[ms[parent[i]][j]].push_back(i);
ms[i].push_back(ms[parent[i]][j]);
}
ms[parent[i]].push_back(i);
ms[i].push_back(parent[i]);
}
}
}
int sol=0;
if(n<=10){
rek(0);
sol=naj;
}
else if(n<=1000){
if(ok==1){
dfs(0, 0);
sol=max(dp[0][0], dp[0][1]);
}
else if(ok==2){
for(int i=0; i<n; i++){
sol+=l[i];
}
}
else if(ok==4){
for(int i=0; i<n; i++){
sol=max(sol, l[i]);
}
}
else{
assert(0);
}
}
else{
assert(0);
}
return sol;
}
