#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "friend.h"
int findSample(int N, int c[], int hs[], int pr[]) {
vi x1(N, 0); // max sum for choose
for (int i = 0; i < N; i++) {
x1[i] = c[i];
}
vi x2(N, 0); // max sum for not choose
for (int i = N - 1; i >= 1; i--) {
if (pr[i] == 2) {
int a = max(x1[hs[i]] + x2[i], x1[i] + x2[hs[i]]);
int b = x2[hs[i]] + x2[i];
x1[hs[i]] = a; x2[hs[i]] = b;
}
else if (pr[i] == 1) {
int a = max(x1[hs[i]] + x1[i], max(x1[hs[i]] + x2[i], x1[i] + x2[hs[i]]));
int b = x2[hs[i]] + x2[i];
x1[hs[i]] = a; x2[hs[i]] = b;
}
else if (pr[i] == 0) {
int a = x1[hs[i]] + x2[i];
int b = max(x1[i] + x2[hs[i]], x2[i] + x2[hs[i]]);
x1[hs[i]] = a; x2[hs[i]] = b;
}
}
/* cout<<"x1: ";
for (int x : x1)
cout<<x<<" ";
cout<<endl;
cout<<"x2: ";
for (int x : x2)
cout<<x<<" ";
cout<<endl;*/
return max(x1[0], x2[0]);
}
