SRM644 div.2 1000 TreeCutting

TreeCutting.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

int cost[64];
Vi edge[64];
const int INF = 1 << 20;

int dfs(int v) {
  int cnt = 0;

  if (cost[v] >= 0) cnt++;
  int cost_sum = cost[v];
  
  for (int child : edge[v]) {
    int child_ret = dfs(child);
    if (child_ret > 0) cnt++;
    cost_sum += child_ret;
  }
  return ((cnt == 0 || (cnt == 1 && cost_sum >= 0)) ? cost_sum : INF);
}

class TreeCutting {
public:
  string can(vector<int> par, vector<int> num) {
    int V = num.size();

    REP(i, V) edge[i].clear();

    REP(i, V) cost[i] = (num[i] > 0 ? num[i] - 1 : num[i]);
    REP(i, V-1) {
      edge[par[i]].push_back(i+1);
    }
    return (!dfs(0) ? "POSSIBLE" : "IMPOSSIBLE");
  }
};