#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
const int MAXN = 100000;
int dp[MAXN][2];//dp[nod][0/1] = suma maxima pe subarborele sau daca l-am ales sau nu pe nod
//doar ca practic este pe arborele care se formeaza de la fiecare nod la hostul lui
int maxim(int a, int b) {
return a > b ? a : b;
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
int i, nod;
for (i = 0; i < n; i++) {
dp[i][1] = confidence[i];
}
for (i = n - 1; i > 0; i--) {
nod = host[i];
if (protocol[i] == 0) {//i are muchie in graf catre nod
dp[nod][1] += dp[i][0];
dp[nod][0] += maxim(dp[i][0], dp[i][1]);
} else if (protocol[i] == 1) {//i are muchie in graf catre cei cu muchie catre nod, deci este ca si cum l-as alege pe nod
dp[nod][1] = maxim(dp[nod][1] + dp[i][0], maxim(dp[nod][1] + dp[i][1], dp[nod][0] + dp[i][1]));
dp[nod][0] += dp[i][0];
} else {//i are muchie catre nod si catre ceilalti catre care are nod muchie
dp[nod][1] = maxim(dp[nod][1] + dp[i][0], dp[nod][0] + dp[i][1]);
dp[nod][0] += dp[i][0];
}
}
return maxim(dp[0][0], dp[0][1]);
}
