#include "friend.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000
#define SMALL 10
int max(int a, int b) { return a > b ? a : b; }
int *ev[1 + N], eo[1 + N];
void append(int u, int v) {
int o = eo[u]++;
if (o >= 2 && (o & o - 1) == 0)
ev[u] = (int *) realloc(ev[u], o * 2 * sizeof *ev[u]);
ev[u][o] = v;
}
int vv[1 + N], uu[1 + N], dd[1 + N], eo_[1 + N], n_;
int bfs() {
static int qu[1 + N];
int u, head, cnt;
for (u = 0; u <= n_; u++)
dd[u] = n_;
head = cnt = 0;
for (u = 1; u <= n_; u++)
if (!vv[u])
dd[u] = 0, qu[head + cnt++] = u;
while (cnt) {
int d, o;
u = qu[cnt--, head++], d = dd[u] + 1;
for (o = eo[u]; o--; ) {
int v = ev[u][o], w = uu[v];
if (dd[w] == n_) {
dd[w] = d;
if (w == 0)
return 1;
qu[head + cnt++] = w;
}
}
}
return 0;
}
int dfs(int u) {
int d, o;
if (u == 0)
return 1;
d = dd[u] + 1;
for (o = eo_[u]; o--; ) {
int v = ev[u][o], w = uu[v];
if (dd[w] == d && dfs(w)) {
vv[u] = v, uu[v] = u;
eo_[u] = o + 1;
return 1;
}
}
dd[u] = n_;
eo_[u] = 0;
return 0;
}
int hopcroft_karp() {
int cnt;
cnt = 0;
while (bfs()) {
int u;
memcpy(eo_, eo, (n_ + 1) * sizeof *eo);
for (u = 1; u <= n_; u++)
if (!vv[u] && dfs(u))
cnt++;
}
return cnt;
}
int findSample(int n, int *aa, int *pp, int *tt) {
static int bb[SMALL], cc[N], dp[N], dq[N];
/*
static int adj[N][N];
*/
int t, i, j, b, ans;
t = tt[0];
for (i = 1; i < n; i++)
if (t != tt[i]) {
t = -1;
break;
}
ans = 0;
if (n <= SMALL) {
for (i = 1; i < n; i++) {
if (tt[i] == 0)
bb[i] = 1 << pp[i];
else if (tt[i] == 1)
bb[i] = bb[pp[i]];
else
bb[i] = bb[pp[i]] | 1 << pp[i];
for (j = 0; j < n; j++)
if ((bb[i] & 1 << j) != 0)
bb[j] |= 1 << i;
}
for (b = 0; b < 1 << n; b++) {
int sum;
sum = 0;
for (i = 0; i < n; i++)
if ((b & 1 << i) != 0) {
if ((bb[i] & b) != 0) {
sum = 0;
break;
}
sum += aa[i];
}
ans = max(ans, sum);
}
} else if (t == 1) {
for (i = 0; i < n; i++)
ans += aa[i];
} else if (t == 2) {
for (i = 0; i < n; i++)
ans = max(ans, aa[i]);
} else if (t == 0) {
for (i = n - 1; i >= 0; i--) {
dp[i] += aa[i];
if (i > 0)
dq[pp[i]] += max(dp[i], dq[i]), dp[pp[i]] += dq[i];
}
ans = max(dp[0], dq[0]);
} else {
/*
for (i = 1; i < n; i++)
if (tt[i] == 0)
adj[i][pp[i]] = adj[pp[i]][i] = 1, cc[i] = cc[pp[i]] ^ 1;
else if (tt[i] == 1) {
for (j = 0; j < n; j++)
if (adj[pp[i]][j])
adj[i][j] = adj[j][i] = 1;
cc[i] = cc[pp[i]];
}
for (i = 1; i <= n; i++)
ev[i] = (int *) malloc(2 * sizeof *ev[i]);
for (i = 0; i < n; i++)
if (cc[i] == 0)
for (j = 0; j < n; j++)
if (cc[j] == 1 && adj[i][j])
append(1 + i, 1 + j);
n_ = n;
ans = n - hopcroft_karp();
*/
}
return ans;
}
