#include "friend.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define debug(x) #x << " = " << x << '\n'
using ll = long long;
// Find out best sample
int findSample(int n, int a[], int parent[], int type[]) {
std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));
for (int i = 0; i < n; i++) {
dp[i][1] = a[i];
}
for (int v = n - 1; v > 0; v--) {
int u = parent[v];
int old0 = dp[u][0];
int old1 = dp[u][1];
if (type[v] == 0) {
dp[u][0] += std::max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
} else if (type[v] == 1) {
dp[u][0] += dp[v][0];
dp[u][1] = std::max({old1 + dp[v][1], old1 + dp[v][0], old0 + dp[v][1]});
} else {
dp[u][0] += dp[v][0];
dp[u][1] = std::max(old1 + dp[v][0], old0 + dp[v][1]);
}
}
return std::max(dp[0][0], dp[0][1]);
}
