#include <vector>
#include "friend.h"
using namespace std;
constexpr int N = 1e5 + 5;
constexpr int ADD = -1;
constexpr int MAX = -2;
pair<int, int> add(const pair<int, int> &p, const pair<int, int> &q) {
return {max(p.first, p.second) + max(q.first, q.second), p.second + q.second};
}
pair<int, int> max(const pair<int, int> &p, const pair<int, int> &q) {
return {max(p.second + q.second, max(p.first + q.second, q.first + p.second)), p.second + q.second};
}
pair<int, int> operator+(const pair<int, int> &p, const pair<int, int> &q) {
return {p.first + q.first, p.second + q.second};
}
inline int collapse(const pair<int, int> &p) {
return max(p.first, p.second);
}
struct Node;
struct NodePtr {
int id;
Node *operator->() const;
};
struct Node {
int token;
int bias, score;
NodePtr left;
NodePtr right;
pair<int, int> evaluate() {
if (token >= 0) return {token + bias, score};
if (token == ADD)
return add(left->evaluate(), right->evaluate()) + pair<int, int>(bias, score);
return max(left->evaluate(), right->evaluate()) + pair<int, int>(bias, score);
}
};
int parent[N];
int ancestor[N];
vector<pair<int, NodePtr>> children[N];
NodePtr roots[N];
NodePtr nodes[N];
int numNodes;
Node pool[N * 2];
Node *NodePtr::operator->() const {
return &pool[id];
}
NodePtr newNode(int token) {
pool[numNodes].token = token;
pool[numNodes].bias = 0;
pool[numNodes].score = 0;
return NodePtr{numNodes++};
}
int dp[N][2];
void dfs(int u) {
dp[u][0] = 0;
for (auto [v, node] : children[u]) {
dfs(v);
node->bias += dp[v][0];
node->score += dp[v][1];
dp[u][0] += dp[v][1];
}
dp[u][1] = collapse(roots[u]->evaluate());
dp[u][1] = max(dp[u][1], dp[u][0]);
}
int findSample(int n, int confidence[], int host[], int protocol[]) {
roots[0] = nodes[0] = newNode(confidence[0]);
ancestor[0] = 0;
parent[0] = 0;
for (int i = 1; i < n; i++) {
int j = host[i];
nodes[i] = newNode(confidence[i]);
if (protocol[i] == '0') {
ancestor[i] = i;
parent[i] = j;
roots[i] = nodes[i];
children[ancestor[j]].push_back({i, nodes[j]});
} else {
ancestor[i] = ancestor[j];
if (protocol[i] == '1') {
nodes[j]->token = ADD;
} else {
nodes[j]->token = MAX;
}
nodes[j]->right = nodes[i];
nodes[j] = nodes[j]->left = newNode(confidence[j]);
}
}
dfs(0);
return dp[0][1];
}
