#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
namespace BRUTE{
const int mxn = 11;
vector<int> paths[mxn];
int GO(int n,int wei[],int host[],int op[]){
for(int i = 1;i<n;i++){
int p = host[i];
if(op[i] == 0){
paths[i].push_back(p);
}
else if(op[i] == 1){
paths[i] = paths[p];
}
else{
paths[i] = paths[p];
paths[i].push_back(p);
}
for(auto &j:paths[i])paths[j].push_back(i);
}
int ans = 0;
for(int i = 0;i<(1<<n);i++){
bool flag = true;
int sum = 0;
for(int j = 0;j<n;j++){
if(!(i&(1<<j)))continue;
sum += wei[j];
for(auto nxt:paths[j]){
if(i&(1<<nxt))flag = false;
}
}
if(!flag)continue;
ans = max(ans,sum);
}
return ans;
}
}
namespace TREE{
const int mxn = 1e5+10;
vector<int> tree[mxn];
int arr[mxn];
int dp[mxn][2];
int ans;
int C = 0;
void dfs(int now){
C++;
dp[now][0] = dp[now][1] = 0;
for(auto nxt:tree[now]){
dfs(nxt);
dp[now][0] += max(dp[nxt][0],dp[nxt][1]);
dp[now][1] += dp[nxt][0];
}
dp[now][1] += arr[now];
ans = max({ans,dp[now][0],dp[now][1]});
return;
}
int GO(int n,int wei[],int host[],int op[]){
for(int i = 0;i<n;i++)arr[i] = wei[i];
for(int i = 1;i<n;i++){
assert(host[i]<i&&host[i]>=0);
tree[host[i]].push_back(i);
}
dfs(0);
assert(C == n);
return ans;
}
}
namespace MLE{
const int mxn = 1010;
int arr[mxn][mxn];
int GO(){
int ans = 0;
for(auto &i:arr)for(auto &j:i)j = rand(),ans ^= j;
return ans;
}
}
// Find out best sample
int findSample(int n,int wei[],int host[],int op[]){
return MLE::GO();
if(n<=10)return BRUTE::GO(n,wei,host,op);
else if(op[1] == 0)return TREE::GO(n,wei,host,op);
else if(op[2] == 1){
int re = 0;
for(int i = 0;i<n;i++)re += wei[i];
return re;
}
else return *max_element(wei,wei+n);
}
