#include<bits/stdc++.h>
#include "friend.h"
#define MAXN 500007
using namespace std;
int n;
vector<int> v[MAXN];
long long ans,cost[MAXN];
int mins,maxs;
bool li[MAXN];
void brute(int x,long long res){
if(x==-1){
ans=max(ans,res);
return;
}
brute(x-1,res);
int br=0;
for(int i:v[x]){
if(li[i])br++;
}
if(br==0){
li[x]=true;
brute(x-1,res+cost[x]);
li[x]=false;
}
}
long long dp[MAXN][2];
bool vis[MAXN][2];
long long ff(int x,int p,int parent){
if(vis[x][p])return dp[x][p];
vis[x][p]=true;
if(p==0){
dp[x][p]=cost[x];
for(int i:v[x]){
if(i==parent)continue;
dp[x][p]+=ff(i,1,x);
}
}
long long sum=0;
for(int i:v[x]){
if(i==parent)continue;
sum+=ff(i,0,x);
}
dp[x][p]=max(dp[x][p],sum);
return dp[x][p];
}
int findSample(int N,int confidence[],int host[],int protocol[]){
//int findSample(int N,vector<int> confidence,vector<int> host,vector<int> protocol){
n=N;
for(int i=0;i<n;i++)cost[i]=confidence[i];
mins=3; maxs=0;
for(int i=1;i<=n-1;i++){
mins=min(mins,protocol[i]);
maxs=max(maxs,protocol[i]);
}
if(mins==maxs and mins==1){
for(int i=0;i<n;i++)ans+=cost[i];
return ans;
}else if(mins==maxs and mins==2){
for(int i=0;i<n;i++)ans=max(ans,cost[i]);
return ans;
}
for(int i=1;i<=n-1;i++){
if(protocol[i]==0 or protocol[i]==2){
v[host[i]].push_back(i);
v[i].push_back(host[i]);
}
if(protocol[i]==1 or protocol[i]==2){
for(int f:v[host[i]]){
v[f].push_back(i);
v[i].push_back(f);
}
}
}
if(n<=20){
brute(n-1,0);
return ans;
}else if(mins==maxs and mins==0){
return ff(0,0,-1);
}
return 1/0;
}
/*int main(){
cout<<findSample(6,{13,3,6,20,10,15},{0,0,0,1,2,0},{0,0,1,2,1,0})<<"\n";
return 0;
}*/
