#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
vector<bool> vis;
vector<vector<int>> E, dp;
void dfs(int x) {
vis[x] = true;
for (auto i : E[x]) {
if (vis[i]) continue;
dfs(i);
dp[x][0] += max(dp[i][1], dp[i][0]); dp[x][1] += dp[i][0];
}
}
int findSample(int n, int cnfd[], int hst[], int prt[]) {
E.assign(n, {});
vector<int> cnt(3);
for (int i = 1; i < n; i++) {
cnt[prt[i]]++;
if (prt[i]) {
for (auto j : E[hst[i]]) {
E[j].push_back(i);
E[i].push_back(j);
}
}
if (prt[i] != 1) {
E[hst[i]].push_back(i);
E[i].push_back(hst[i]);
}
}
if (!cnt[2]) {
vector<int> v(n);
for (int i = 0; i < n; i++) {
vis.assign(n, false);
dp.assign(n, vector<int>(2));
for (int i = 0; i < n; i++)
dp[i][1] = cnfd[i];
dfs(i);
v[i] = max(dp[i][0], dp[i][1]);
}
int sm = 0;
vis.assign(n, false);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int mx = v[i];
queue<int> q;
q.push(i); vis[i] = true;
while (!q.empty()) {
int x = q.front(); q.pop();
for (auto j : E[x]) {
if (!vis[j]) {
vis[j] = true;
mx = max(mx, v[j]);
q.push(j);
}
}
}
sm += mx;
}
return sm;
}
else if (cnt[0] == n - 1) {
vis.assign(n, false);
dp.assign(n, vector<int>(2));
for (int i = 0; i < n; i++)
dp[i][1] = cnfd[i];
dfs(0);
return max(dp[0][0], dp[0][1]);
}
else if (cnt[1] == n - 1) {
int sm = 0;
for (int i = 0; i < n; i++)
sm += cnfd[i];
return sm;
}
else if (cnt[2] == n - 1) {
int sm = 0;
vector<bool> vis(n);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
int mx = cnfd[i];
for (auto j : E[i]) {
vis[j] = true;
mx = max(mx, cnfd[j]);
}
sm += mx;
}
return sm;
}
assert(false);
}
