#include "friend.h"
#include <tuple>
#include <algorithm>
#include <utility>
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;
/*
Solve from last query
We can maintain (A, B) for each node where
A is MWIS with current node used
B is MWIS without current node used
By running backwrds, we "merge" two nodes into one.
*/
pii ar[100001];
int findSample(int n, int confidence[], int host[], int protocol[]){
for (int i = 0; i < n; i++) {ar[i].fst = confidence[i];}
for (int i = n - 1; i; i--)
{
if (protocol[i] == 0) ar[host[i]] = make_pair(ar[host[i]].fst + ar[i].snd, ar[host[i]].snd + max(ar[i].fst, ar[i].snd));
else if (protocol[i] == 1) ar[host[i]] = make_pair(max({ar[host[i]].fst + ar[i].fst, ar[host[i]].fst + ar[i].snd, ar[host[i]].snd + ar[i].fst}), ar[host[i]].snd + ar[i].snd);
else ar[host[i]] = make_pair(max(ar[host[i]].fst + ar[i].snd, ar[i].fst + ar[host[i]].snd), ar[host[i]].snd + ar[i].snd);
}
return max(ar[0].fst, ar[0].snd);
}
