#include "friend.h"
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
const int N = 1e4 + 123;
vector<int>g[N];
int c[N];
int used[N];
void dfs(int v, int &a, int &b) {
a += c[v];
used[v] = 1;
for (int to : g[v]) if (!used[to]) {
dfs(to, b, a);
}
}
vector<int>vec;
int pr[N];
void go(int v) {
used[v] = 1;
for (int to : g[v]) if (to != pr[v]) {
if (used[to]) {
if (vec.size()) continue;
int y = v;
while (y != to) {
vec.emplace_back(y);
y = pr[y];
}
vec.emplace_back(to);
} else {
pr[to] = v;
go(to);
}
}
}
int X[N], Y[N];
int dp[N][2];
int findSample(int n,int confidence[],int host[],int protocol[]){
for (int i = 0 ; i < n ; ++ i) {
c[i] = confidence[i];
}
for (int i = 1 ; i < n ; ++ i) {
int j = host[i];
g[j].emplace_back(i);
g[i].emplace_back(j);
}
int ans = 0;
for (int i = 0 ; i < n ; ++ i) {
if (used[i]) continue;
vec.clear();
pr[i] = -1;
go(i);
for (int j = 0 ; j < n ; ++ j) used[j] = 0;
if (!vec.size()) {
int a = 0, b = 0;
dfs(i, a, b);
ans += max(a, b);
continue;
}
for (int j : vec) used[j] = 1;
int m = vec.size();
for (int j = 0 ; j < m ; ++ j) {
dfs(vec[j], X[j], Y[j]);
}
dp[0][0] = Y[0];
dp[0][1] = 0;
for (int j = 1 ; j < m ; ++ j) {
dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j];
dp[j][1] = dp[j - 1][0] + X[j];
}
int cur = dp[m - 1][0];
cur = max(cur, dp[m - 1][1]);
dp[0][0] = 0;
dp[0][1] = X[0];
for (int j = 1 ; j < m ; ++ j) {
dp[j][0] = max(dp[j - 1][0], dp[j - 1][1]) + Y[j];
dp[j][1] = dp[j - 1][0] + X[j];
}
cur = max(cur, dp[m - 1][0]);
ans += cur;
}
return ans;
}
