#include "friend.h"
int min( int a, int b ) { return a < b ? a : b; }
int max( int a, int b ) { return a > b ? a : b; }
int findSample( int n, int confidence[], int host[], int protocol[] ) {
int *choose = new int[n];
int *not_choose = new int[n];
for( int i = 0 ; i < n ; i++ ){
choose[i] = confidence[i];
not_choose[i] = 0;
}
for( int i = n - 1 ; i > 0 ; i-- ){
// we merge the two nodes (i, host[i]) into one single node
// this explains the wierd asignment of sums
if( protocol[i] == 0 ){
int new_choose = choose[host[i]] + not_choose[i]; // choose host[i] and not i
int new_not_choose = not_choose[host[i]] + max( choose[i], not_choose[i] ); // choose i and not host[i] or choose none
choose[host[i]] = new_choose;
not_choose[host[i]] = new_not_choose;
}else if( protocol[i] == 1 ){
// if we choose any of the two nodes that means we choose the merged node
int new_choose = max( choose[i] + choose[host[i]], max( choose[i] + not_choose[i], not_choose[i] + choose[host[i]] ) );
int new_not_choose = not_choose[host[i]] + not_choose[i];
choose[host[i]] = new_choose;
not_choose[host[i]] = new_not_choose;
}else{
int new_choose = max( choose[host[i]] + not_choose[i], not_choose[host[i]] + choose[i] );
int new_not_choose = not_choose[i] + not_choose[host[i]];
choose[host[i]] = new_choose;
not_choose[host[i]] = new_not_choose;
}
}
int ret = max( choose[0], not_choose[0] );
delete []choose;
delete []not_choose;
return ret;
}
