#include "friend.h" #define N 1000 #define SMALL 10 int max(int a, int b) { return a > b ? a : b; } int findSample(int n, int *aa, int *pp, int *tt) { static int bb[SMALL], dp[N], dq[N]; int i, j, b, ans; 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 (tt[1] == 1) { for (i = 0; i < n; i++) ans += aa[i]; } else if (tt[1] == 2) { for (i = 0; i < n; i++) ans = max(ans, aa[i]); } else { 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]); } return ans; }