#include <bits/stdc++.h>
using namespace std;
vector<int> dp0, dp1;
int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf);
int dfs0(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
if (dp0[u] != -1) return dp0[u];
dp0[u] = 0;
for (int v: adj[u]) {
if (v == p) continue;
dp0[u] += max(dfs0(v, u, adj, conf), dfs1(v, u, adj, conf));
}
return dp0[u];
}
int dfs1(int u, int p, vector<vector<int>>& adj, vector<int>& conf) {
if (dp1[u] != -1) return dp1[u];
dp1[u] = conf[u];
for (int v: adj[u]) {
if (v == p) continue;;
dp1[u] += dfs0(v, u, adj, conf);
}
return dp1[u];
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
if (n <= 20) {
vector<vector<int>> adj(n, vector<int>(n, 0));
for (int i = 1; i < n; ++i) {
if (protocol[i] == 0 || protocol[i] == 2)
adj[host[i]][i] = adj[i][host[i]] = 1;
if (protocol[i] == 1 || protocol[i] == 2) {
for (int j = 0; j < n; ++j) {
if (adj[j][host[i]]) adj[i][j] = adj[j][i] = 1;
}
}
}
int ans = 0;
vector<int> c((1<<n), 0);
queue<int> q;
q.push(0);
while (!q.empty()) {
int mask = q.front();
q.pop();
for (int i = 0; i < n; ++i) {
if (mask&(1<<i)) continue;
bool ok = true;
for (int j = 0; j < n && ok; ++j) {
if (j == i) continue;
if (mask&(1<<j) && adj[i][j]) ok = false;
}
if (ok) {
c[mask|(1<<i)] = c[mask]+confidence[i];
ans = max(ans, c[mask|(1<<i)]);
q.push(mask|(1<<i));
}
}
}
return ans;
}
vector<vector<int>> adj(n);
bool b0 = true, b1 = true, b2 = true;
for (int i = 1; i < n; ++i) {
if (protocol[i] == 0) b1 = b2 = false;
else if (protocol[i] == 1) b0 = b2 = false;
else b0 = b1 = false;
adj[host[i]].push_back(i);
adj[i].push_back(host[i]);
}
if (b1) {
int ans = 0;
for (int i = 0; i < n; ++i) ans += confidence[i];
return ans;
}
if (b2) {
int ans = 0;
for (int i = 0; i < n; ++i) ans = max(ans, confidence[i]);
return ans;
}
dp0 = dp1 = vector<int>(n, -1);
vector<int> conf(n);
for (int i = 0; i < n; ++i) conf[i] = confidence[i];
return max(dfs0(0, 0, adj, conf), dfs1(0, 0, adj, conf));
}
