Submission #19442403

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
bool dfs(vector<vector<int>> &t,vector<int> &x,vector<int> &mi,int i){
  vector<bool> a(x.at(i)+1,0);
  a[0]=1;
  int s=0;
  for(int j:t.at(i)){
    if(!dfs(t,x,mi,j))
      return 0;
    s+=x.at(j)+mi.at(j);
    for(int k=x.at(i);k>=0;k--){
      if(!a[k])
        continue;
      a[k]=0;
      if(k+x.at(j)<=x.at(i))
        a[k+x.at(j)]=1;
      if(k+mi.at(j)<=x.at(i))
        a[k+mi.at(j)]=1;
    }
  }
  for(int k=x.at(i);k>=0;k--){
    if(a[k]){
      mi.at(i)=s-k;
      return 1;
    }
  }
  return 0;
}   
int main(){
  int n;
  cin>>n;
  vector<vector<int>> t(n);
  for(int i=1;i<n;i++){
    int p;
    cin>>p;
    p--;
    t.at(p).push_back(i);
  }
  vector<int> x(n);
  for(int i=0;i<n;i++)
    cin>>x.at(i);
  vector<int> mi(n);
  cout<<(dfs(t,x,mi,0)?"POSSIBLE":"IMPOSSIBLE")<<endl;
}

Submission Info

Judge Result