#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int lim=1e5+100;
int ty[lim];
int dp[6][lim];
int a[lim];
vector<int>v[lim];
int dpp[6];
bool isroot[lim],isclean[lim];
void dfs(int node,int par){
dp[1][node]=dp[4][node]=a[node];
for(int j:v[node]){
if(j==par)continue;
dfs(j,node);
if(ty[j]==0){
dpp[0]=dp[0][node]+dp[0][j];
dpp[1]=dp[1][node]+dp[0][j];
dpp[2]=dp[2][node]+dp[1][j];
dpp[3]=dp[3][node]+dp[1][j];
dpp[4]=dp[4][node]+dp[0][j];
dpp[5]=dp[5][node]+dp[1][j];
}
if(ty[j]==1){
dpp[0]=dp[0][node]+dp[0][j];
dpp[1]=dp[1][node]+dp[0][j];
dpp[2]=dp[2][node]+dp[0][j];
dpp[3]=max(dp[3][node]+dp[0][j],dp[0][node]+dp[1][j]);
dpp[4]=max(dp[4][node]+dp[0][j],dp[1][node]+dp[1][j]);
dpp[5]=dp[5][node]+dp[0][j];
}
if(ty[j]==2){
dpp[0]=dp[0][node]+dp[0][j];
dpp[1]=dp[1][node]+dp[0][j];
dpp[2]=dp[2][node]+dp[0][j];
dpp[3]=dp[3][node]+dp[0][j];
dpp[4]=dp[4][node]+dp[0][j];
dpp[5]=max(dp[5][node]+dp[0][j],dp[0][node]+dp[1][j]);
}
for(int i=0;i<6;i++){
dp[i][node]=dpp[i];
}
}
/*
cerr<<node<<" "<<a[node]<<" ------ \n";
for(int i=0;i<6;i++){
cerr<<dp[i][node]<<" ";
}cerr<<"\n\n";
*/
dp[0][node]=max(dp[0][node],dp[2][node]);
dp[1][node]=max({dp[0][node],dp[1][node],dp[3][node],dp[4][node],dp[5][node]});
}
int findSample(int n,int confidence[],int host[],int protocol[]){
isroot[0]=isclean[0]=1;
a[0]=confidence[0];
for(int i=1;i<n;i++){
ty[i]=protocol[i];
a[i]=confidence[i];
if(ty[i]==1&&isclean[host[i]]){
isroot[i]=isclean[i]=1;
}
else{
v[host[i]].pb(i);
isclean[host[i]]=0;
}
}
int ans=0;
for(int i=0;i<n;i++){
if(isroot[i]){
dfs(i,-1);
ans+=dp[1][i];
}
}
return ans;
}
