#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
vector<vector<pair<int, int>>> graph;
vector<int> value;
vector<bool> visited;
pair<int, int> dfs(int v) {
if (visited[v]) return {0, 0};
visited[v] = 1;
cerr << v << "\n";
pair<int, int> res = {value[v], 0};
for (auto i: graph[v]) {
pair<int, int> tmp = dfs(i.first);
if (i.second == 0) {
res.first += tmp.second;
res.second += tmp.first;
}
if (i.second == 1) {
res.first += tmp.first;
res.second += tmp.second;
}
if (i.second == 2) {
res.first += tmp.second;
res.second = max(res.second, tmp.first);
}
}
res.first = max(res.first, res.second);
cerr << res.first << " " << res.second << "\n";
return res;
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
value.clear();
graph.clear();
graph.resize(n);
value.resize(n);
for (int i = 0; i<n; i++) value[i] = confidence[i];
for (int i=1; i<n; i++) {
graph[i].push_back({host[i], protocol[i]});
graph[host[i]].push_back({i, protocol[i]});
}
visited.assign(n, 0);
return dfs(0).first;
}
