#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
struct UnionFind{
vector<int> par;
UnionFind(int n){
par.resize(n);
iota(par.begin(),par.end(),0);
}
int find(int i){
if(par[i] == i) return i;
return par[i] = find(par[i]);
}
void unite(int i, int j){
i = find(i);
j = find(j);
par[j] = i;
}
};
vector<int> arr,dpT, dpN;
vector<vector<int>> adj;
void DFS(int v){
dpT[v] = arr[v];
int oth1 = 0;
for(auto u : adj[v]){
DFS(u);
dpT[v] += dpN[u];
dpN[v] += max(dpT[u],dpN[u]);
}
}
// Find out best sample
int findSample(int n,int confidence[],int host[],int protocol[]){
int ans=0;
adj.resize(n);
arr.resize(n);
arr[0] = confidence[0];
UnionFind uf(n);
for(int i = 1; i < n; i++){
if(protocol[i] == 0){
adj[host[i]].push_back(i);
arr[i] = confidence[i];
}else{
uf.unite(host[i],i);
int real =uf.find(i);
arr[real] += confidence[i];
}
}
dpN = dpT = vector<int>(n);
DFS(0);
for(int i = 0; i < n; i++){
ans = max({ans, dpT[i], dpN[i]});
}
return ans;
}
