#include "friend.h"
#include <bits/stdc++.h>
using namespace std;
// ----------------------- 答えを求める関数 --------------------------
int N, A[100009], ty[100009], B[100009], col[100009], dp[100009][2], toku[100009];
vector<int>X[100009], E[100009]; int parcol[100009], par[100009], lim[100009];
vector<pair<int, int>>D[100009][2];
void dfs(int pos) {
for (int i = 0; i < (int)X[pos].size(); i++) dfs(X[pos][i]);
// 0 : 全部白 1 : 一個以上黒
for (int i = 0; i <= E[pos].size(); i++) { D[i][0].clear(); D[i][1].clear(); }
for (int i = 0; i < (int)X[pos].size(); i++) dp[pos][0] += max(dp[X[pos][i]][0], dp[X[pos][i]][1]);
int S = 0; for (int i = 0; i < (int)X[pos].size(); i++) S += dp[X[pos][i]][0];
map<int, int>Map; for (int i = 0; i < (int)E[pos].size(); i++) Map[E[pos][i]] = i;
for (int i = 0; i < (int)X[pos].size(); i++) {
int EE = Map[par[X[pos][i]]];
D[EE + 1][0].push_back(make_pair(EE, X[pos][i]));
D[lim[X[pos][i]]][1].push_back(make_pair(EE, X[pos][i]));
//cout << pos << " " << EE << " " << lim[X[pos][i]] << endl;
}
int SR = 0, maxn = 0; for (int i = 0; i < (int)X[pos].size(); i++) SR += toku[X[pos][i]];
maxn = SR; vector<int> cnt(E[pos].size(), 0);
for (int i = 1; i <= (int)E[pos].size(); i++) {
SR += A[E[pos][i - 1]];
for (pair<int, int> t : D[i][0]) {
int V1 = cnt[t.first], V2 = cnt[t.first] + toku[t.second]; V1 -= A[E[pos][t.first]]; V2 -= A[E[pos][t.first]];
cnt[t.first] += toku[t.second]; SR -= toku[t.second];
SR += max(V2, 0) - max(V1, 0);
}
maxn = max(maxn, SR);
for (pair<int, int> t : D[i][1]) {
int V1 = cnt[t.first], V2 = cnt[t.first] - toku[t.second]; V1 -= A[E[pos][t.first]]; V2 -= A[E[pos][t.first]];
cnt[t.first] -= toku[t.second];
SR += max(V2, 0) - max(V1, 0);
}
}
dp[pos][1] = S + maxn;
toku[pos] = max(dp[pos][1], dp[pos][0]) - dp[pos][0];
}
int solve() {
E[0].push_back(0);
for (int i = 1; i < N; i++) {
if (ty[i] == 0) {
col[i] = i;
parcol[i] = col[B[i]];
par[i] = B[i];
lim[i] = E[parcol[i]].size();
X[parcol[i]].push_back(i);
E[col[i]].push_back(i);
}
if (ty[i] == 1) {
col[i] = col[B[i]];
E[col[i]].push_back(i);
}
}
/*for (int i = 0; i < N; i++) {
printf("% 3d: col =% 3d, parcol =% 3d, par =% 3d, lim =% 3d, ", i, col[i], parcol[i], par[i], lim[i]);
printf("X = {"); for (int j = 0; j < X[i].size(); j++) { if (j) printf(","); printf("% 3d", X[i][j]); } printf("}, ");
printf("E = {"); for (int j = 0; j < E[i].size(); j++) { if (j) printf(","); printf("% 3d", E[i][j]); } printf("}\n");
}*/
dfs(0);
/*cout << "--- DP TABLE ---" << endl;
for (int i = 0; i < N; i++) {
if (dp[i][0] == 0 && dp[i][1] == 0) continue;
printf("% 3d: % 3d, % 3d\n", i, dp[i][0], dp[i][1]);
}*/
return max(dp[0][0], dp[0][1]);
}
// --------------------------- 場合分け -----------------------------
int findSample(int n,int confidence[],int host[],int protocol[]){
int bit = 0;
for (int i = 1; i <= n - 1; i++) bit |= (1 << protocol[i]);
if (bit <= 3) {
N = n;
for (int i = 0; i < N; i++) A[i] = confidence[i];
for (int i = 1; i < N; i++) { ty[i] = protocol[i]; B[i] = host[i]; }
return solve();
}
if (bit == 4) {
// Subtask 3.
int sum = 0; for (int i = 0; i < n; i++) sum = max(sum, confidence[i]);
return sum;
}
if (n <= 10) {
// Subtask 1.
vector<int>G[10];
for (int i = 1; i <= n - 1; i++) {
if (protocol[i] == 0 || protocol[i] == 2) {
G[host[i]].push_back(i);
G[i].push_back(host[i]);
}
if (protocol[i] == 1 || protocol[i] == 2) {
for (int pos : G[host[i]]) {
if (pos == i) continue;
G[pos].push_back(i);
G[i].push_back(pos);
}
}
}
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
bool flag = false; int sum = 0;
int bit[10]; for (int j = 0; j < n; j++) { bit[j] = (i / (1 << j)) % 2; sum += bit[j] * confidence[j]; }
for (int j = 0; j < n; j++) {
for (int k = 0; k < G[j].size(); k++) { if (bit[j] == 1 && bit[G[j][k]] == 1) flag = true; }
}
if (flag == false) ans = max(ans, sum);
}
return ans;
}
return -1;
}
