#include "friend.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)
#define f first
#define s second
void iayf(int n, int i, int host, vector<vector<int>> &adjList) {
adjList[host].push_back(i);
adjList[i].push_back(host);
}
void mfayf(int n, int i, int host, vector<vector<int>> &adjList) {
for (auto j : adjList[host]) {
adjList[j].push_back(i);
adjList[i].push_back(j);
}
}
void wayf(int n, int i, int host, vector<vector<int>> &adjList) {
mfayf(n,i,host,adjList);
iayf(n, i, host, adjList);
}
int memoing(int n, int node, int parent, vector<vector<int>> &adjList, vector<pair<int,int> > &memo, int confidence[]) {
if (memo[node].f == -1) {
if (adjList[node].size()==1 && parent!=-1) { //leaf
memo[node].f =0;
memo[node].s = confidence[node];
}
else {
int sm=0, sm2=confidence[node];
for (auto j : adjList[node]) {
sm += memoing(n, j, node, adjList, memo, confidence);
sm2 += memo[j].f;
}
memo[node].f= sm; memo[node].s= sm2;
}
}
return max(memo[node].f, memo[node].s);
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
vector<vector<int> > adjList(n);
REP(1,i,n) {
if (protocol[i]==0) iayf(n,i,host[i],adjList);
else if (protocol[i]==1) mfayf(n,i,host[i],adjList);
else if (protocol[i]==2) wayf(n,i,host[i],adjList);
}
vector<pair<int,int> > memo(n,{-1,-1});
return memoing(n,0,-1,adjList,memo,confidence);
}
