ARC083E Bichrome Tree

未分类

$x$ 的子树中所有点对 $x$ 的父亲的贡献在颜色相同时是 $X_x$，颜色不相同时是 $sum_x - X_x$，$sun_x$ 是 $x$ 的子树和。发现只要所有子树的贡献不超过 $X_i$，$i$ 结点可以随便填一个数来满足限制。那么贪心的想就是要所有子树能够造成的贡献最小也就是 $sum_x$ 最小。因为一棵子树内所有点的相对颜色已经确定，再怎么翻转也不影响本来的答案，所以两种情况可以直接枚举，做一遍 DP 将所有的贡献可能算出来，取一个最大且不超过 $X_i$ 的即是最优的决策，此时 $sum_i$ 最小。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int MAXN = 1000;
int n, edge;
int X[MAXN | 1], fst[MAXN | 1];
int sum[MAXN | 1], dp[MAXN | 1][5001];
struct Edge {
  int to, nxt;
  Edge() : to(0), nxt(0) {}
  Edge(int a, int b) : to(b), nxt(fst[a]) {}
} e[MAXN];
inline int read() {
  register int x = 0;
  register char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
inline void addEdge(int a, int b) {
  e[++edge] =  Edge(a, b);
  fst[a] = edge;
}
void DP(int x) {
  int size = 0;
  for (int k = fst[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    DP(to);
    sum[x] += sum[to];
    ++size;
  }
  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
  for (int i = 1, k = fst[x]; k; k = e[k].nxt, ++i) {
    int to = e[k].to;
    for (int j = 0; j <= X[x]; ++j) {
      if (j >= X[to]) dp[i][j] |= dp[i - 1][j - X[to]];
      if (j >= sum[to] - X[to]) dp[i][j] |= dp[i - 1][j - sum[to] + X[to]];
    }
  }
  bool flag = false;
  for (int i = X[x]; i >= 0; --i) {
    if (dp[size][i]) {
      flag = true;
      sum[x] += X[x] - i;
      break;
    }
  }
  if (!flag) {
    puts("IMPOSSIBLE");
    exit(0);
  }
}
int main() {
  n = read();
  for (int i = 2; i <= n; ++i) addEdge(read(), i);
  for (int i = 1; i <= n; ++i) X[i] = read();
  DP(1);
  puts("POSSIBLE");
  return 0;
}