#include "friend.h"
#pragma GCC target("avx2,popcnt,sse4")
#pragma GCC optimize("O3,unroll-loops")
#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 BIP{
const int mxn = 1022;
bitset<mxn> adj[mxn];
bitset<mxn> vis,side;
int n;
int mat[mxn];
bool dfs(int now){
if(vis[now])return false;
vis[now] = true;
for(int nxt = 0;nxt<n;nxt++){
if(!adj[now][nxt])continue;
if(mat[nxt] == -1||dfs(mat[nxt])){
mat[nxt] = now;
mat[now] = nxt;
return true;
}
}
return false;
}
int GO(int nn,int wei[],int host[],int op[]){
n = nn;
for(int i = 1;i<n;i++){
int p = host[i];
if(op[i] == 0){
adj[p][i] = adj[i][p] = 1;
side[i] = (side[p]?0:1);
}
else{
for(int j = 0;j<n;j++){
adj[i][j] = adj[j][i] = adj[p][j];
}
side[i] = side[p];
}
}
int ans = 0;
memset(mat,-1,sizeof(mat));
for(int i = 0;i<n;i++){
vis.reset();
if(side[i])ans += dfs(i);
}
return n-ans;
}
}
// Find out best sample
int findSample(int n,int wei[],int host[],int op[]){
return BIP::GO(n,wei,host,op);
if(n<=10)return BRUTE::GO(n,wei,host,op);
else if(op[1] == 0||op[1] == 1)return BIP::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);
}
