// 19.07
#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 100111
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
int val[maxn], root[maxn], dp[maxn][2];
vector<pii> edge;
vector<int> adj[maxn];
bool used[maxn];
int rooting(int x){
if(root[x] == x)
return x;
return root[x] = rooting(root[x]);
}
void DFS(int x, int p){
dp[x][0] = 0;
dp[x][1] = val[x];
used[x] = 1;
for(int v : adj[x]){
if(v == p)
continue;
DFS(v, x);
}
for(int v : adj[x]){
if(v == p)
continue;
dp[x][0] += max(dp[v][1], dp[v][0]);
dp[x][1] += dp[v][0];
}
}
int findSample(int n, int confidence[], int host[], int protocol[]){
for(int i = 0; i < n; i++){
val[i] = confidence[i];
root[i] = i;
}
for(int i = n - 1; i > 0; i--){
int a = host[i];
int b = i;
if(protocol[i] == 0)
edge.pb(mp(a, b));
if(protocol[i] != 0){
int ra = rooting(a);
int rb = rooting(b);
root[rb] = ra;
if(protocol[i] == 1)
val[ra] += val[rb];
if(protocol[i] == 2)
val[ra] = max(val[ra], val[rb]);
val[rb] = 0;
}
}
for(pii e : edge){
int a = rooting(e.fi);
int b = rooting(e.se);
adj[a].pb(b);
adj[b].pb(a);
}
int ans = 0;
for(int i = 0; i < n; i++){
if(!used[i]){
DFS(i, -1);
ans += max(dp[i][0], dp[i][1]);
}
}
return ans;
}
