#include "friend.h"
#include <vector>
#include <algorithm>
using namespace std;
int c[1006], dp[1006][2];
vector<int> adj[1006];
int dfs(int x, int y, int prev = -1) {
if (dp[x][y] + 1) return dp[x][y];
dp[x][y] = 0;
if (y) dp[x][y] += c[x];
for (auto &i: adj[x]) if (i != prev) {
if (y) dp[x][y] += dfs(i, 0, x);
else dp[x][y] += max(dfs(i, 0, x), dfs(i, 1, x));
}
return dp[x][y];
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
fill(dp[0], dp[1005] + 2, -1);
for (int i = 0; i < n; i++) c[i] = confidence[i];
if (protocol[1] == 1) {
int res = 0;
for (int i = 0; i < n; i++) res += confidence[i];
return res;
} else if (protocol[1] == 2) {
int res = 0;
for (int i = 0; i < n; i++) res = max(res, confidence[i]);
return res;
} else {
for (int i = 1; i < n; i++) {
adj[i].push_back(host[i]);
adj[host[i]].push_back(i);
}
return max(dfs(0, 0), dfs(0, 1));
}
}
