#include <bits/stdc++.h>
#include "friend.h"
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
int par[MAXN] , sz[MAXN] , val[MAXN] , dp[2][MAXN] , mark[MAXN];
vector<int> adj[MAXN];
vector<pii> E;
int Find(int v){
return (par[v] == -1 ? v : par[v] = Find(par[v]));
}
void Union(int v , int u , int flag){
v = Find(v); u = Find(u);
if(v == u) return;
if(sz[v] < sz[u]) swap(v , u);
par[u] = v; sz[v] += sz[u];
if(flag == 0) val[v] += val[u];
if(flag == 1) val[v] = max(val[v] , val[u]);
}
void DFS(int v , int p = -1){
mark[v] = 1;
dp[1][v] = val[v];
for(int u : adj[v]){
if(u == p) continue;
DFS(u , v);
dp[0][v] += max(dp[0][u] , dp[1][u]);
dp[1][v] += dp[0][u];
}
}
int findSample(int n,int confidence[],int host[],int protocol[]){
for(int i = 0 ; i < n ; i++){
val[i] = confidence[i];
par[i] = -1; sz[i] = 1;
}
for(int i = 1 ; i < n ; i++){
if(protocol[i] == 0){
E.push_back({i , host[i]});
}
else{
Union(i , host[i] , (protocol[i] == 2));
}
}
for(pii i : E){
adj[Find(i.X)].push_back(Find(i.Y));
adj[Find(i.Y)].push_back(Find(i.X));
}
int ans = 0;
for(int i = 1 ; i <= n ; i++){
if(i == Find(i) && !mark[i]){
DFS(i);
ans += max(dp[0][i] , dp[1][i]);
}
}
return ans;
}
